<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html><head><title>SRFI 41: Streams</title></head><body>

<h1>Title</h1>

Streams


<h1>Author</h1>

Philip L. Bewig

<h1>Status</h1>

This SRFI is currently in ``final'' status. To see an explanation of each
status that a SRFI can hold, see
<a href="http://srfi.schemers.org/srfi-process.html">here</a>.
To comment on this SRFI, please <code>
<a href="mailto:srfi%20minus%2041%20at%20srfi%20dot%20schemers%20dot%20org">mailto:srfi minus 41 at srfi dot schemers dot org</a></code>.
See <a href="http://srfi.schemers.org/srfi-list-subscribe.html">instructions
here</a> to subscribe to the list. You can access
the discussion via
<a href="http://srfi.schemers.org/srfi-41/mail-archive/maillist.html">
the archive of the mailing list</a>.
You can access
post-finalization messages via
<a href="http://srfi.schemers.org/srfi-41/post-mail-archive/maillist.html">
the archive of the mailing list</a>.

<ul>
<li>Received: <a href="http://srfi.schemers.org/cgi-bin/viewcvs.cgi/*checkout*/srfi/srfi-41/srfi-41.html?rev=1.2">2007/10/24</a>
</li><li>Revised: <a href="http://srfi.schemers.org/cgi-bin/viewcvs.cgi/*checkout*/srfi/srfi-41/srfi-41.html?rev=1.3">2007/11/14</a>
</li><li>Revised: <a href="http://srfi.schemers.org/cgi-bin/viewcvs.cgi/*checkout*/srfi/srfi-41/srfi-41.html?rev=1.5">2007/11/14</a>
</li><li>Revised: <a href="http://srfi.schemers.org/cgi-bin/viewcvs.cgi/*checkout*/srfi/srfi-41/srfi-41.html?rev=1.6">2007/12/17</a>
</li><li>Final: <a href="http://srfi.schemers.org/cgi-bin/viewcvs.cgi/*checkout*/srfi/srfi-41/srfi-41.html?rev=1.7">2008/01/24</a>
</li><li>Draft: 2007/10/21 - 2007/12/22
</li></ul>
  
<h1>Abstract</h1>

<p align="justify"><font face="serif">Streams, sometimes 
called lazy lists, are a sequential data structure containing elements 
computed only on demand.  A stream is either null or is a pair 
with a stream in its cdr.  Since elements of a stream are computed 
only when accessed, streams can be infinite.  Once computed, the 
value of a stream element is cached in case it is needed again.</font></p>

<p align="justify"><font face="serif">Streams without 
memoization were first described by Peter Landin in 1965.  Memoization 
became accepted as an essential feature of streams about a decade later.  
Today, streams are the signature data type of functional programming 
languages such as Haskell.</font></p>

<p align="justify"><font face="serif">This Scheme Request for Implementation describes 
two libraries for operating on streams: a canonical set of stream primitives
and a set of procedures and syntax derived from those primitives that permits
convenient expression of stream operations. They rely on facilities provided
by R6RS, including libraries, records, and error reporting.  To load both
stream libraries, say:</font></p>

<p align="justify"><font face="monospace">(import (streams))</font></p>

<h1>Rationale</h1>

<p align="justify"><font face="serif">Harold Abelson 
and Gerald Jay Sussman discuss streams at length, giving a strong justification 
for their use.  The streams they provide are represented as a </font><font face="monospace">cons</font><font face="serif"> 
pair with a promise to return a stream in its </font><font face="monospace">cdr</font><font face="serif">; for instance, a stream with elements 
the first three counting numbers is represented conceptually as </font><font face="monospace">(cons 1 (delay (cons 2 (delay (cons 3 (delay 
'()))))))</font><font face="serif">.</font><font face="monospace">  </font><font face="serif">Philip Wadler, Walid Taha and David 
MacQueen describe such streams as <i>odd</i> because, regardless of 
their length, the parity of the number of constructors (</font><font face="monospace">delay</font><font face="serif">, </font><font face="monospace">cons</font><font face="serif">, </font><font face="monospace">'()</font><font face="serif">) 
in the stream is odd.</font></p>

<p align="justify"><font face="serif">The streams 
provided here differ from those of Abelson and Sussman, being 
represented as promises that contain a </font><font face="monospace">cons</font><font face="serif"> pair with a stream in its </font><font face="monospace">cdr</font><font face="serif">; 
for instance, the stream with elements the first three counting numbers 
is represented conceptually as </font><font face="monospace">(delay 
(cons 1 (delay (cons 2 (delay (cons 3 (delay '())))))))</font><font face="serif">; 
this is an <i>even</i> stream because the parity of the number of constructors 
in the stream is even.</font></p>

<p align="justify"><font face="serif">Even streams 
are more complex than odd streams in both definition and usage, but 
they offer a strong benefit: they fix the off-by-one error of odd streams.  
Wadler, Taha and MacQueen show, for instance, that an expression like </font><font face="monospace">(stream-&gt;list 4 (stream-map / (stream-from 
4 -1))) </font><font face="serif">evaluates to </font><font face="monospace">(1/4 1/3 1/2 1)</font><font face="serif"> 
using even streams but fails with a divide-by-zero error using odd streams, 
because the next element in the stream, which will be </font><font face="monospace">1/0</font><font face="serif">, is evaluated before it is accessed.  
This extra bit of laziness is not just an interesting oddity; it is 
vitally critical in many circumstances, as will become apparent below.</font></p>

<p align="justify"><font face="serif">When used effectively, 
the primary benefit of streams is improved modularity.  Consider 
a process that takes a sequence of items, operating on each in turn.  
If the operation is complex, it may be useful to split it into two or 
more procedures in which the partially-processed sequence is an intermediate 
result.  If that sequence is stored as a list, the entire intermediate 
result must reside in memory all at once; however, if the intermediate 
result is stored as a stream, it can be generated piecemeal, using only 
as much memory as required by a single item.  This leads to a programming 
style that uses many small operators, each operating on the sequence 
of items as a whole, similar to a pipeline of unix commands.</font></p>

<p align="justify"><font face="serif">In addition 
to improved modularity, streams permit a clear exposition of backtracking 
algorithms using the &#8220;stream of successes&#8221; technique, and they can 
be used to model generators and co-routines.  The implicit memoization 
of streams makes them useful for building persistent data structures, 
and the laziness of streams permits some multi-pass algorithms to be 
executed in a single pass.  Savvy programmers use streams to enhance 
their programs in countless ways.</font></p>

<p align="justify"><font face="serif">There is an 
obvious space/time trade-off between lists and streams; lists take more 
space, but streams take more time (to see why, look at all the type 
conversions in the implementation of the stream primitives).  Streams 
are appropriate when the sequence is truly infinite, when the space 
savings are needed, or when they offer a clearer exposition of the algorithms 
that operate on the sequence.</font></p>


<h1>Specification</h1>

<h2>The <font face="monospace">(streams primitive)</font><font face="serif"> library</font></h2>

<font face="serif">The </font><font face="monospace">(streams primitive)</font><font face="serif"> 
library provides two mutually-recursive abstract data types:  An 
object of the </font><font face="monospace">stream</font><font face="serif"> abstract data type is a promise that, 
when forced, is either </font><font face="monospace">stream-null</font><font face="serif"> or is an object of type </font><font face="monospace">stream-pair</font><font face="serif">.  
An object of the </font><font face="monospace">stream-pair</font><font face="serif"> abstract data type contains a </font><font face="monospace">stream-car</font><font face="serif"> 
and a </font><font face="monospace">stream-cdr</font><font face="serif">, which must be a </font><font face="monospace">stream</font><font face="serif">.  The essential feature of streams 
is the systematic suspensions of the recursive promises between the 
two data types.</font><p></p>

<p align="justify"><font face="monospace"><pre>&#945; stream
  :: (promise stream-null)
  |  (promise (&#945; stream-pair))</pre><pre>&#945; stream-pair
  :: (promise &#945;) × (promise (&#945; stream))</pre></font></p>

<p align="justify"><font face="serif">The object 
stored in the </font><font face="monospace">stream-car</font><font face="serif"> of a </font><font face="monospace">stream-pair</font><font face="serif"> is a promise that is forced the first 
time the </font><font face="monospace">stream-car</font><font face="serif"> is accessed; its value is cached in 
case it is needed again.  The object may have any type, and different 
stream elements may have different types.  If the </font><font face="monospace">stream-car</font><font face="serif"> is never accessed, the object stored 
there is never evaluated.  Likewise, the </font><font face="monospace">stream-cdr</font><font face="serif"> is a promise to return a stream, and 
is only forced on demand.</font></p>

<p align="justify"><font face="serif">This library 
provides eight operators: constructors for </font><font face="monospace">stream-null</font><font face="serif"> and </font><font face="monospace">stream-pair</font><font face="serif">s, type recognizers for streams and 
the two kinds of streams, accessors for both fields of a </font><font face="monospace">stream-pair</font><font face="serif">, 
and a lambda that creates procedures that return streams.</font></p>

<p align="justify"><font face="serif"><b>constructor: </b></font><font face="monospace"><b>stream-null</b></font><br>
<font face="monospace">Stream-null</font><font face="serif"> is a promise that, when forced, is 
a single object, distinguishable from all other objects, that represents 
the null stream.  </font><font face="monospace">Stream-null</font><font face="serif"> is immutable and unique.</font></p>

<p align="justify"><font face="monospace"><font face="serif"><b>constructor: </b></font><b>(stream-cons </b></font><font face="serif"><b><i>object</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream-cons</font><font face="serif"> is a macro that accepts an <i>object</i> 
and a <i>stream</i> and creates a newly-allocated </font><font face="monospace">stream</font><font face="serif"> containing a promise that, when forced, 
is a </font><font face="monospace">stream-pair</font><font face="serif"> with the <i>object</i> in its </font><font face="monospace">stream-car</font><font face="serif"> 
and the <i>stream</i> in its </font><font face="monospace">stream-cdr</font><font face="serif">.  </font><font face="monospace">Stream-cons</font><font face="serif"> must be syntactic, not procedural, 
because neither <i>object</i> nor <i>stream</i> is evaluated when </font><font face="monospace">stream-cons</font><font face="serif"> 
is called.  Since <i>stream</i> is not evaluated, when the stream-pair 
is created, it is not an error to call </font><font face="monospace">stream-cons</font><font face="serif"> with a <i>stream</i> that is not of 
type </font><font face="monospace">stream</font><font face="serif">; 
however, doing so will cause an error later when the </font><font face="monospace">stream-cdr</font><font face="serif"> of the </font><font face="monospace">stream-pair</font><font face="serif"> is accessed.  Once created, a </font><font face="monospace">stream-pair</font><font face="serif"> 
is immutable; there is no </font><font face="monospace">stream-set-car!</font><font face="serif"> or </font><font face="monospace">stream-set-cdr!</font><font face="serif"> that modifies an existing </font><font face="monospace">stream-pair</font><font face="serif">.  
There is no dotted-pair or improper stream as with lists.</font></p>

<p align="justify"><font face="serif"><b>recognizer: </b></font><font face="monospace"><b>(stream? </b></font><font face="serif"><b><i>object</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream?</font><font face="serif"> is a procedure that takes an <i>object</i> 
and returns </font><font face="monospace">#t</font><font face="serif"> 
if the <i>object</i> is a stream and </font><font face="monospace">#f</font><font face="serif"> otherwise.  If <i>object</i> 
is a stream, </font><font face="monospace">stream?</font><font face="serif"> does not force its promise.  
If </font><font face="monospace">(stream? obj)</font><font face="serif"> is </font><font face="monospace">#t</font><font face="serif">, then one of </font><font face="monospace">(stream-null? 
obj)</font><font face="serif"> and </font><font face="monospace">(stream-pair? 
obj)</font><font face="serif"> will be </font><font face="monospace">#t</font><font face="serif"> 
and the other will be </font><font face="monospace">#f</font><font face="serif">; if </font><font face="monospace">(stream? 
obj)</font><font face="serif"> is </font><font face="monospace">#f</font><font face="serif">, both </font><font face="monospace">(stream-null? 
obj)</font><font face="serif"> and </font><font face="monospace">(stream-pair? 
obj)</font><font face="serif"> will be </font><font face="monospace">#f</font><font face="serif">. </font></p>

<p align="justify"><font face="serif"><b>recognizer: </b></font><font face="monospace"><b>(stream-null? </b></font><font face="serif"><b><i>object</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream-null?</font><font face="serif"> is a procedure that takes an <i>object</i> 
and returns </font><font face="monospace">#t</font><font face="serif"> 
if the <i>object</i> is the distinguished null stream and </font><font face="monospace">#f</font><font face="serif"> 
otherwise.  If <i>object</i> is a stream, </font><font face="monospace">stream-null?</font><font face="serif"> must force its promise in order to 
distinguish </font><font face="monospace">stream-null</font><font face="serif"> from </font><font face="monospace">stream-pair</font><font face="serif">.</font></p>

<p align="justify"><font face="serif"><b>recognizer: </b></font><font face="monospace"><b>(stream-pair? </b></font><font face="serif"><b><i>object</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream-pair?</font><font face="serif"> is a procedure that takes an <i>object</i> 
and returns </font><font face="monospace">#t</font><font face="serif"> 
if the <i>object</i> is a </font><font face="monospace">stream-pair</font><font face="serif"> constructed by </font><font face="monospace">stream-cons</font><font face="serif"> and </font><font face="monospace">#f</font><font face="serif"> otherwise.  If <i>object</i> 
is a stream, </font><font face="monospace">stream-pair?</font><font face="serif"> must force its promise in order to 
distinguish </font><font face="monospace">stream-null</font><font face="serif"> from </font><font face="monospace">stream-pair</font><font face="serif">.</font></p>

<p align="justify"><font face="serif"><b>accessor: </b></font><font face="monospace"><b>(stream-car </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream-car</font><font face="serif"> is a procedure that takes a <i>stream</i> 
and returns the object stored in the </font><font face="monospace">stream-car</font><font face="serif"> of the <i>stream</i>.  </font><font face="monospace">Stream-car</font><font face="serif"> 
signals an error if the object passed to it is not a </font><font face="monospace">stream-pair</font><font face="serif">.  Calling </font><font face="monospace">stream-car</font><font face="serif"> causes the object stored there to 
be evaluated if it has not yet been; the object&#8217;s value is cached 
in case it is needed again.</font></p>

<p align="justify"><font face="serif"><b>accessor: </b></font><font face="monospace"><b>(stream-cdr </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream-cdr</font><font face="serif"> is a procedure that takes a <i>stream</i> 
and returns the stream stored in the </font><font face="monospace">stream-cdr</font><font face="serif"> of the <i>stream</i>.  </font><font face="monospace">Stream-cdr</font><font face="serif"> 
signals an error if the object passed to it is not a </font><font face="monospace">stream-pair</font><font face="serif">.  Calling </font><font face="monospace">stream-cdr</font><font face="serif"> 
does not force the promise containing the stream stored in the
</font><font face="monospace">stream-cdr</font><font face="serif"> of the <i>stream</i>.

</font></p><p align="justify"><font face="serif"><font face="serif"><b>lambda: </b></font><font face="serif"><b>(</b></font><font face="monospace"><b>stream-lambda </b></font><font face="serif"><b><i>args</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>body</i>)</b></font><br>
<font face="monospace">Stream-lambda</font><font face="serif"> creates a procedure that returns a 
promise to evaluate the <i>body</i> of the procedure.  The last <i>
body</i> expression to be evaluated must yield a stream.  As with 
normal </font><font face="monospace">lambda</font><font face="serif">, <i>
args</i> may be a single variable name, in which case all the formal 
arguments are collected into a single list, or a list of variable names, 
which may be null if there are no arguments, proper if there are an 
exact number of arguments, or dotted if a fixed number of arguments 
is to be followed by zero or more arguments collected into a list.  <i>
Body</i> must contain at least one expression, and may contain internal 
definitions preceding any expressions to be evaluated.</font></font></p>

<p align="justify"><font face="serif"><font face="monospace"></font></font></p><pre><font face="serif"><font face="monospace">(define strm123
  (stream-cons 1
    (stream-cons 2
      (stream-cons 3
        stream-null))))</font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="monospace">(stream-car strm123) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
1</font></font></p>

<p align="justify"><font face="serif"><font face="monospace">(stream-car (stream-cdr 
strm123) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
2</font></font></p>

<p align="justify"><font face="serif"><font face="monospace"></font></font></p><pre><font face="serif"><font face="monospace">(stream-pair?
  (stream-cdr
    (stream-cons (/ 1 0) stream-null))) </font><font face="Symbol">&#8658;</font><font face="monospace"> #f</font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="monospace">(stream? (list 
1 2 3)) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
#f</font></font></p>

<p align="justify"><font face="serif"><font face="monospace"></font></font></p><pre><font face="serif"><font face="monospace">(define iter
  (stream-lambda (f x)
    (stream-cons x (iter f (f x)))))</font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="monospace">(define nats (iter 
(lambda (x) (+ x 1)) 0))</font></font></p>

<p align="justify"><font face="serif"><font face="monospace">(stream-car (stream-cdr 
nats)) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
1</font></font></p>

<p align="justify"><font face="serif"><font face="monospace"></font></font></p><pre><font face="serif"><font face="monospace">(define stream-add
  (stream-lambda (s1 s2)
    (stream-cons
      (+ (stream-car s1) (stream-car s2))
      (stream-add (stream-cdr s1)
                  (stream-cdr s2)))))</font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="monospace">(define evens (stream-add 
nats nats))</font></font></p>

<p align="justify"><font face="serif"><font face="monospace">(stream-car evens) </font><font face="Symbol">&#8658;</font><font face="monospace"> 0</font></font></p>

<p align="justify"><font face="serif"><font face="monospace">(stream-car (stream-cdr 
evens)) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
2</font></font></p>

<p align="justify"><font face="serif"><font face="monospace">(stream-car (stream-cdr 
(stream-cdr evens))) </font><font face="Symbol">&#8658;</font><font face="monospace"> 4</font></font></p>

<h2><font face="serif">The <font face="monospace">(streams derived)</font><font face="serif"> library</font></font></h2>

<p align="justify"><font face="serif"><font face="serif">The </font><font face="monospace">(streams derived)</font><font face="serif"> 
library provides useful procedures and syntax that depend on the primitives 
defined above.  In the operator 
templates given below, an ellipsis </font><font face="monospace">...</font><font face="serif"> indicates zero or more repetitions 
of the preceding subexpression and square brackets </font><font face="monospace">[&#8230;]</font><font face="serif"> indicate optional elements.  
In the type annotations given below, square brackets </font><font face="monospace">[&#8230;]</font><font face="serif"> refer to lists, curly braces </font><font face="monospace">{&#8230;}</font><font face="serif"> 
refer to streams, and </font><font face="monospace">nat</font><font face="serif"> refers to exact non-negative integers.</font></font></p>

<p align="justify"><font face="serif"><font face="serif"><b>syntax: </b></font><font face="monospace"><b>(define-stream 
(</b></font><font face="serif"><b><i>name</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>args</i></b></font><font face="monospace"><b>) </b></font><font face="serif"><b><i>body</i></b></font><font face="monospace"><b>) </b></font><br>
<font face="monospace">Define-stream</font><font face="serif"> creates a procedure that returns a 
stream, and may appear anywhere a normal </font><font face="monospace">define</font><font face="serif"> may appear, including as an internal 
definition, and may have internal definitions of its own, including 
other </font><font face="monospace">define-stream</font><font face="serif">s.  The defined procedure takes 
arguments in the same way as </font><font face="monospace">stream-lambda</font><font face="serif">.  </font><font face="monospace">Define-stream</font><font face="serif"> is syntactic sugar on </font><font face="monospace">stream-lambda</font><font face="serif">; 
see also </font><font face="monospace">stream-let</font><font face="serif">, which is also a sugaring of </font><font face="monospace">stream-lambda</font><font face="serif">.</font></font></p>

<p align="justify"><font face="serif"><font face="serif">A simple version of <font face="monospace">stream-map</font>
<font face="serif"> that takes only a single input stream calls itself recursively:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-map proc strm)
  (if (stream-null? strm)
      stream-null
      (stream-cons
        (proc (stream-car strm))
        (stream-map proc (stream-cdr strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(list-&gt;stream </b></font><font face="serif"><b><i>list-of-objects</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">[&#945;] &#8594; {&#945;}</font><br>
<font face="monospace">List-&gt;stream</font><font face="serif"> takes a list of objects and returns 
a newly-allocated stream containing in its elements the objects in the 
list.  Since the objects are given in a list, they are evaluated 
when </font><font face="monospace">list-&gt;stream</font><font face="serif"> is called, before the stream is created.  
If the list of objects is null, as in </font><font face="monospace">(list-&gt;stream 
'())</font><font face="serif">, the null stream is 
returned.  See also </font><font face="monospace">stream</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define strm123 (list-&gt;stream '(1 2 3)))</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">
<pre>; fails with divide-by-zero error
(define s (list-&gt;stream (list 1 (/ 1 0) -1)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(port-&gt;stream 
[</b></font><font face="serif"><b><i>port</i></b></font><font face="monospace"><b>])</b></font><br>
<font face="monospace">port &#8594; {char}</font><br>
<font face="monospace">Port-&gt;stream</font><font face="serif"> takes a <i>port</i> and returns a 
newly-allocated stream containing in its elements the characters on 
the port.  If <i>port</i> is not given it defaults to the current 
input port.  The returned stream has finite length and is terminated 
by </font><font face="monospace">stream-null</font><font face="serif">.</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="serif">It looks like 
one use of </font><font face="monospace">port-&gt;stream</font><font face="serif"> would be this:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define s ;wrong!
  (with-input-from-file filename
    (lambda () (port-&gt;stream))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">But that fails, 
because </font><font face="monospace">with-input-from-file</font><font face="serif"> is eager, and closes the input port 
prematurely, before the first character is read.  To read a file 
into a stream, say:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (file-&gt;stream filename)
  (let ((p (open-input-file filename)))
    (stream-let loop ((c (read-char p)))
      (if (eof-object? c)
          (begin (close-input-port p)
                 stream-null)
          (stream-cons c
            (loop (read-char p)))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>syntax: </b></font><font face="monospace"><b>(stream </b></font><font face="serif"><b><i>object</i> </b></font><font face="monospace"><b>...)</b></font><br>
<font face="monospace">Stream</font><font face="serif"> is syntax that takes zero or more <i>
object</i>s and creates a newly-allocated stream containing in its elements 
the <i>object</i>s, in order.  Since </font><font face="monospace">stream</font><font face="serif"> is syntactic, the <i>object</i>s are 
evaluated when they are accessed, not when the stream is created.  
If no <i>object</i>s are given, as in </font><font face="monospace">(stream)</font><font face="serif">, the null stream is returned.  
See also </font><font face="monospace">list-&gt;stream</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define strm123 (stream 1 2 3))</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>; (/ 1 0) not evaluated when stream is created
(define s (stream 1 (/ 1 0) -1))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(stream-&gt;list 
[</b></font><font face="serif"><b><i>n</i></b></font><font face="monospace"><b>] </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">nat × {&#945;} &#8594; [&#945;]</font><br>
<font face="monospace">Stream-&gt;list</font><font face="serif"> takes a natural number <i>n</i> and 
a <i>stream</i> and returns a newly-allocated list containing in its 
elements the first <i>n</i> items in the <i>stream</i>. If the <i>stream</i> 
has less than <i>n</i> items all the items in the <i>stream</i> will 
be included in the returned list.  If <i>n</i> is not given it 
defaults to infinity, which means that unless <i>stream</i> is finite </font><font face="monospace">stream-&gt;list</font><font face="serif"> 
will never return.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(stream-&gt;list 10
  (stream-map (lambda (x) (* x x))
    (stream-from 0)))
  </font><font face="Symbol">&#8658;</font><font face="monospace"> (0 1 4 9 16 25 36 49 64 81)</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b>
</font><font face="monospace"><b>(stream-append </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b> ...)</b></font><br>
<font face="monospace">{&#945;} ... &#8594; {&#945;}</font><br>
<font face="monospace">Stream-append</font><font face="serif"> returns a newly-allocated stream containing 
in its elements those elements contained in its input <i>stream</i>s, 
in order of input.  If any of the input <i>stream</i>s is infinite, 
no elements of any of the succeeding input <i>stream</i>s will appear 
in the output stream; thus, if </font><font face="monospace">x</font><font face="serif"> is infinite, </font><font face="monospace">(stream-append 
x y) &#8801; x</font><font face="serif">.  See also </font><font face="monospace">stream-concat</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Quicksort can 
be used to sort a stream, using </font><font face="monospace">stream-append</font><font face="serif"> to build the output; the sort is lazy; 
so if only the beginning of the output stream is needed, the end of 
the stream is never sorted.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (qsort lt? strm)
  (if (stream-null? strm)
      stream-null
      (let ((x (stream-car strm))
            (xs (stream-cdr strm)))
        (stream-append
          (qsort lt?
            (stream-filter
              (lambda (u) (lt? u x))
              xs))
          (stream x)
          (qsort lt?
            (stream-filter
              (lambda (u) (not (lt? u x)))
              xs))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Note also that, 
when used in tail position as in </font><font face="monospace">qsort</font><font face="serif">, </font><font face="monospace">stream-append</font><font face="serif"> does not suffer the poor performance 
of </font><font face="monospace">append</font><font face="serif"> 
on lists.  The list version of </font><font face="monospace">append</font><font face="serif"> requires re-traversal of all its list 
arguments except the last each time it is called.  But </font><font face="monospace">stream-append</font><font face="serif"> 
is different.  Each recursive call to </font><font face="monospace">stream-append</font><font face="serif"> is suspended; when it is later forced, 
the preceding elements of the result have already been traversed, so 
tail-recursive loops that produce streams are efficient even when each 
element is appended to the end of the result stream.  This also 
implies that during traversal of the result only one promise needs to 
be kept in memory at a time.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(stream-concat </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">{{&#945;}} ... &#8594; {&#945;}</font><br>
<font face="monospace">Stream-concat</font><font face="serif"> takes a <i>stream</i> consisting of 
one or more streams and returns a newly-allocated stream containing 
all the elements of the input streams.  If any of the streams in 
the input <i>stream</i> is infinite, any remaining streams in the input <i>
stream</i> will never appear in the output stream.  See also </font><font face="monospace">stream-append</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-&gt;list
  (stream-concat
    (stream
      (stream 1 2) (stream) (stream 3 2 1))))
  &#8658; (1 2 3 2 1)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The permutations 
of a finite stream can be determined by interleaving each element of 
the stream in all possible positions within each permutation of the 
other elements of the stream.  </font><font face="monospace">Interleave</font><font face="serif"> returns a stream of streams with <i>
x</i> inserted in each possible position of <i>yy</i>:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (interleave x yy)
  (stream-match yy
    (() (stream (stream x)))
    ((y . ys)
      (stream-append
        (stream (stream-cons x yy))
        (stream-map
          (lambda (z) (stream-cons y z))
          (interleave x ys))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (perms xs)
  (if (stream-null? xs)
      (stream (stream))
      (stream-concat
        (stream-map
          (lambda (ys)
            (interleave (stream-car xs) ys))
          (perms (stream-cdr xs))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(stream-constant </b></font><font face="serif"><b><i>object</i></b></font><font face="monospace"><b> ...)</b></font><br>
<font face="monospace">&#945; ... &#8594; {&#945;}</font><br>
<font face="monospace">Stream-constant</font><font face="serif"> takes one or more <i>object</i>s and 
returns a newly-allocated stream containing in its elements the <i>object</i>s, 
repeating the <i>object</i>s in succession forever.</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-constant 
1) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
1 1 1 ...</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-constant 
#t #f) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
#t #f #t #f #t #f ...</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(stream-drop </b></font><font face="serif"><b><i>n</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><font face="serif"><b> procedure </b></font><br>
<font face="monospace">nat × {&#945;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-drop</font><font face="serif"> returns the suffix of the input <i>
stream</i> that starts at the next element after the first <i>n</i> 
elements.  The output stream shares structure with the input <i>
stream</i>; thus, promises forced in one instance of the stream are 
also forced in the other instance of the stream.  If the input <i>
stream</i> has less than <i>n</i> elements, </font><font face="monospace">stream-drop</font><font face="serif"> returns the null stream.  See 
also </font><font face="monospace">stream-take</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-split n strm)
  (values (stream-take n strm)
          (stream-drop n strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font><font face="monospace"><b>(stream-drop-while </b></font><font face="serif"><b><i>pred?</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">(&#945; &#8594; boolean) × {&#945;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-drop-while</font><font face="serif"> returns the suffix of the input <i>
stream</i> that starts at the first element <i>x</i> for which </font><font face="monospace">(pred? </font><font face="serif"><i>x</i></font><font face="monospace">)</font><font face="serif"> 
is </font><font face="monospace">#f</font><font face="serif">.  
The output stream shares structure with the input <i>stream</i>.  
See also </font><font face="monospace">stream-take-while</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-unique</font><font face="serif"> creates a new stream that retains 
only the first of any sub-sequences of repeated elements.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-unique eql? strm)
  (if (stream-null? strm)
      stream-null
      (stream-cons (stream-car strm)
        (stream-unique eql?
          (stream-drop-while
            (lambda (x)
              (eql? (stream-car strm) x))
            strm)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-filter </b></font><font face="serif"><b><i>pred?</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">(&#945; &#8594; boolean) × {&#945;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-filter</font><font face="serif"> returns a newly-allocated stream that 
contains only those elements <i>x</i> of the input <i>stream</i> for 
which </font><font face="monospace">(</font><font face="serif"><i>pred?</i></font><font face="monospace"> </font><font face="serif"><i>x</i></font><font face="monospace">)</font><font face="serif"> 
is non-</font><font face="monospace">#f</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-filter odd? (stream-from 0))
   &#8658; 1 3 5 7 9 ...</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-fold </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>base</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">(&#945; × &#946; &#8594; &#945;) × &#945; × {&#946;} &#8594; &#945;</font><br>
<font face="monospace">Stream-fold</font><font face="serif"> applies a binary <i>proc</i>edure 
to <i>base</i> and the first element of <i>stream</i> to compute a new <i>
base</i>, then applies the <i>proc</i>edure to the new <i>base</i> and 
the next element of <i>stream</i> to compute a succeeding <i>base</i>, 
and so on, accumulating a value that is finally returned as the value 
of </font><font face="monospace">stream-fold</font><font face="serif"> 
when the end of the <i>stream</i> is reached.  <i>Stream</i> must 
be finite, or </font><font face="monospace">stream-fold</font><font face="serif"> will enter an infinite loop.  
See also </font><font face="monospace">stream-scan</font><font face="serif">, which is similar to </font><font face="monospace">stream-fold</font><font face="serif">, but useful for infinite streams.  
For readers familiar with other functional languages, this is a left-fold; 
there is no corresponding right-fold, since right-fold relies on finite 
streams that are fully-evaluated, at which time they may as well be 
converted to a list.</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-fold</font><font face="serif"> is often used to summarize a stream 
in a single value, for instance, to compute the maximum element of a stream.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-maximum lt? strm)
  (stream-fold
    (lambda (x y) (if (lt? x y) y x))
    (stream-car strm)
    (stream-cdr strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Sometimes, 
it is useful to have </font><font face="monospace">stream-fold</font><font face="serif"> defined only on non-null streams:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-fold-one proc strm)
  (stream-fold proc
    (stream-car strm)
    (stream-cdr strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-minimum</font><font face="serif"> can then be defined as:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-minimum lt? strm)
  (stream-fold-one
    (lambda (x y) (if (lt? x y) x y))
    strm))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-fold</font><font face="serif"> can also be used to build a stream:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (isort lt? strm)
    (define-stream (insert strm x)
      (stream-match strm
        (() (stream x))
        ((y . ys)
          (if (lt? y x)
              (stream-cons y (insert ys x))
              (stream-cons x strm)))))
    (stream-fold insert stream-null strm))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-for-each </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b> ...)</b></font><br>
<font face="monospace">(&#945; × &#946; × ...) × {&#945;} × {&#946;} ...</font><br>
<font face="monospace">Stream-for-each</font><font face="serif"> applies a <i>proc</i>edure element-wise 
to corresponding elements of the input <i>stream</i>s for its side-effects; 
it returns nothing.  </font><font face="monospace">Stream-for-each</font><font face="serif"> stops as soon as any of its input <i>
stream</i>s is exhausted.</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="serif">The following 
procedure displays the contents of a file:</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (display-file filename)
  (stream-for-each display
    (file-&gt;stream filename)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">
<font face="serif"><b>procedure: </b></font>
<b>(stream-from </b></font><font face="serif"><b><i>first</i></b></font><font face="monospace"><b> 
[</b></font><font face="serif"><b><i>step</i></b></font><font face="monospace"><b>])</b></font><br>
<font face="monospace">number × number &#8594; {number}</font><br>
<font face="monospace">Stream-from</font><font face="serif"> creates a newly-allocated stream that 
contains <i>first</i> as its first element and increments each succeeding 
element by <i>step</i>.  If <i>step</i> is not given it defaults 
to </font><font face="monospace">1</font><font face="serif">.  <i>
First</i> and <i>step</i> may be of any numeric type.  </font><font face="monospace">Stream-from</font><font face="serif"> 
is frequently useful as a generator in </font><font face="monospace">stream-of</font><font face="serif"> expressions.  See also </font><font face="monospace">stream-range</font><font face="serif"> 
for a similar procedure that creates finite streams.</font><font face="monospace"> </font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-from</font><font face="serif"> could be implemented as </font><font face="monospace">(stream-iterate (lambda (x) (+ x </font><font face="serif"><i>step</i></font><font face="monospace">)) </font><font face="serif"><i>first</i></font><font face="monospace">)</font><font face="serif">.</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define nats (stream-from 
0)) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
0 1 2 ...</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define odds (stream-from 
1 2)) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
1 3 5 ...</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-iterate proc base)</b></font><br>
<font face="monospace">(&#945; &#8594; &#945;) × &#945; &#8594; {&#945;}</font><br>
<font face="monospace">Stream-iterate</font><font face="serif"> creates a newly-allocated stream containing <i>
base</i> in its first element and applies <i>proc</i> to each element 
in turn to determine the succeeding element.  See also </font><font face="monospace">stream-unfold</font><font face="serif"> 
and </font><font face="monospace">stream-unfolds</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-iterate (lambda (x) (+ x 1)) 0)
  &#8658; 0 1 2 3 4 ...</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(stream-iterate (lambda (x) (* x 2)) 1)
  &#8658; 1 2 4 8 16 ...</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Given a <i>
seed</i> between </font><font face="monospace">0</font><font face="serif"> and </font><font face="monospace">2<sup>32</sup></font><font face="serif">, exclusive, the following expression 
creates a stream of pseudo-random integers between </font><font face="monospace">0</font><font face="serif"> and </font><font face="monospace">2<sup>32</sup></font><font face="serif">, exclusive, beginning with <i>seed</i>, 
using the method described by Stephen Park and Keith Miller:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(stream-iterate
  (lambda (x) (modulo (* x 16807) 2147483647))
  </font><font face="serif"><i>seed</i></font><font face="monospace">)</font></font></font></pre><p></p>

<p><font face="serif"><font face="serif"><font face="serif">Successive values of the continued 
fraction shown below approach the value of the &#8220;golden ratio&#8221; &#966; 
&#8776; 1.618:</font></font></font></p>

<p align="center"><font face="serif"><font face="serif"><img src="srfi-41_files/streams1.jpg" alt="Continued fraction" height="126" width="131"></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The fractions 
can be calculated by the stream</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-iterate 
(lambda (x) (+ 1 (/ x))) 1)</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-length </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">{&#945;} &#8594; nat</font><br>
<font face="monospace">Stream-length</font><font face="serif"> takes an input <i>stream</i> and returns 
the number of elements in the <i>stream</i>; it does not evaluate its 
elements.  </font><font face="monospace">Stream-length</font><font face="serif"> may only be used on finite streams; 
it enters an infinite loop with infinite streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-length 
strm123) </font><font face="Symbol">&#8658;</font><font face="monospace"> 
3</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>syntax: </b></font>
<font face="monospace"><b>(stream-let </b></font><font face="serif"><b><i>tag</i></b></font><font face="monospace"><b> 
((</b></font><font face="serif"><b><i>var</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>expr</i></b></font><font face="monospace"><b>) ...) </b></font><font face="serif"><b><i>body</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">Stream-let</font><font face="serif"> creates a local scope that binds each <i>
var</i>iable<i> </i>to the value of its corresponding <i>expr</i>ession.  
It additionally binds <i>tag</i> to a procedure which takes the bound <i>
var</i>iables as arguments and <i>body</i> as its defining expressions, 
binding the <i>tag</i> with </font><font face="monospace">stream-lambda</font><font face="serif">. <i>Tag</i> is in scope within <i>
body</i>, and may be called recursively.  When the expanded expression 
defined by the </font><font face="monospace">stream-let</font><font face="serif"> is evaluated, </font><font face="monospace">stream-let</font><font face="serif"> evaluates the expressions in its <i>
body</i> in an environment containing the newly-bound <i>var</i>iables, 
returning the value of the last expression evaluated, which must yield 
a stream.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-let</font><font face="serif"> provides syntactic sugar on </font><font face="monospace">stream-lambda</font><font face="serif">, 
in the same manner as normal </font><font face="monospace">let</font><font face="serif"> provides syntactic sugar on normal </font><font face="monospace">lambda</font><font face="serif">.  
However, unlike normal </font><font face="monospace">let</font><font face="serif">, the <i>tag</i> is required, not optional, 
because unnamed </font><font face="monospace">stream-let</font><font face="serif"> is meaningless. </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-member</font><font face="serif"> returns the first stream-pair of the 
input </font><font face="monospace">strm</font><font face="serif"> 
with a </font><font face="monospace">stream-car</font><font face="serif"> <i>x</i> that satisfies </font><font face="monospace">(eql? obj </font><font face="serif"><i>x</i></font><font face="monospace">)</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-member eql? obj strm)
  (stream-let loop ((strm strm))
    (cond ((stream-null? strm) #f)
          ((eql? obj (stream-car strm)) strm)
          (else (loop (stream-cdr strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-map </b></font><font face="serif"><b><i>proc stream</i> </b></font><font face="monospace"><b>...)</b></font><br>
<font face="monospace">(&#945; × &#946; ... &#8594; &#969;) × {&#945;} × {&#946;} ... &#8594; {&#969;}</font><br>
<font face="monospace">Stream-map</font><font face="serif"> applies a <i>proc</i>edure element-wise 
to corresponding elements of the input <i>stream</i>s, returning a newly-allocated 
stream containing elements that are the results of those <i>proc</i>edure 
applications.  The output stream has as many elements as the minimum-length 
input <i>stream</i>, and may be infinite.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define (square 
x) (* x x))</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-map square 
(stream 9 3)) &#8658; 81 9</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (sigma f m n)
  (stream-fold + 0
    (stream-map f (stream-range m (+ n 1)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(sigma square 1 
100) &#8658; 338350</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">In some functional 
languages, </font><font face="monospace">stream-map</font><font face="serif"> takes only a single input stream, 
and </font><font face="monospace">stream-zipwith</font><font face="serif"> provides a companion function that 
takes multiple input streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>syntax: </b></font>
<font face="monospace"><b>(stream-match </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>clause</i></b></font><font face="monospace"><b> ...)</b></font><br>
<font face="monospace">Stream-match</font><font face="serif"> provides the syntax of pattern-matching 
for streams.  The input <i>stream</i> is an expression that evaluates 
to a stream.  Clauses are of the form </font><font face="monospace">(</font><font face="serif"><i>pattern</i></font><font face="monospace"> 
[</font><font face="serif"><i>fender</i></font><font face="monospace">] </font><font face="serif"><i>expr</i></font><font face="monospace">)</font><font face="serif">, 
consisting of a <i>pattern</i> that matches a stream of a particular 
shape, an optional <i>fender</i> that must succeed if the pattern is 
to match, and an <i>expr</i>ession that is evaluated if the <i>pattern</i> 
matches.  There are four types of <i>pattern</i>s:</font></font></font></p>

<ul type="disc">
<font face="serif"><font face="serif">  <li><font face="monospace">()</font><font face="serif"> 
  &#8212; Matches the null stream.</font></li>
  <li><font face="monospace">(</font><font face="serif"><i>pat</i><sub><i>0</i></sub></font><font face="monospace"> </font><font face="serif"><i>pat</i><sub><i>1</i></sub></font><font face="monospace"> ...)</font><font face="serif"> 
  &#8212; Matches a finite stream with length exactly equal to the number 
  of pattern elements.</font></li>
  <li><font face="monospace">(</font><font face="serif"><i>pat</i><sub><i>0</i></sub></font><font face="monospace"> </font><font face="serif"><i>pat</i><sub><i>1</i></sub></font><font face="monospace"> ... . </font><font face="serif"><i>pat</i><sub><i>rest</i></sub></font><font face="monospace">)</font><font face="serif"> 
  &#8212; Matches an infinite stream, or a finite stream with length at least 
  as great as the number of pattern elements before the literal dot.</font></li>
  <li><font face="serif"><i>pat</i> &#8212; Matches 
  an entire stream.  Should always appear last in the list of clauses; 
  it&#8217;s not an error to appear elsewhere, but subsequent clauses could 
  never match.</font></li>
</font></font></ul>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Each pattern 
element <i>pat</i><sub><i>i</i></sub> may be either:</font></font></font></p>

<ul type="disc">
<font face="serif"><font face="serif">  <li><font face="serif">An identifier &#8212; 
  Matches any stream element.  Additionally, the value of the stream 
  element is bound to the variable named by the identifier, which is in 
  scope in the <i>fender</i> and <i>expr</i>ession of the corresponding <i>clause</i>.  
  Each identifier in a single pattern must be unique.</font></li>
  <li><font face="serif">A literal underscore 
  &#8212; Matches any stream element, but creates no bindings.</font></li>
</font></font></ul>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The <i>pattern</i>s 
are tested in order, left-to-right, until a matching pattern is found; 
if <i>fender</i> is present, it must evaluate as non-</font><font face="monospace">#f</font><font face="serif"> for the match to be successful.  
Pattern variables are bound in the corresponding <i>fender</i> and <i>
expr</i>ession.  Once the matching pattern is found, the corresponding <i>
expr</i>ession is evaluated and returned as the result of the match.  
An error is signaled if no pattern matches the input <i>stream</i>.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-match</font><font face="serif"> is often used to distinguish null 
streams from non-null streams, binding </font><font face="monospace">head</font><font face="serif"> and </font><font face="monospace">tail</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (len strm)
  (stream-match strm
    (() 0)
    ((head . tail) (+ 1 (len tail)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Fenders can 
test the common case where two stream elements must be identical; the </font><font face="monospace">else</font><font face="serif"> 
pattern is an identifier bound to the entire stream, not a keyword as 
in </font><font face="monospace">cond</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-match strm
  ((x y . _) (equal? x y) 'ok)
  (else 'error))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">A more complex 
example uses two nested matchers to match two different stream arguments; </font><font face="monospace">(stream-merge lt? . </font><font face="serif"><i>strms</i></font><font face="monospace">)</font><font face="serif"> 
stably merges two or more streams ordered by the </font><font face="monospace">lt?</font><font face="serif"> predicate:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-merge lt? . strms)
  (define-stream (merge xx yy)
    (stream-match xx (() yy) ((x . xs)
      (stream-match yy (() xx) ((y . ys)
        (if (lt? y x)
            (stream-cons y (merge xx ys))
            (stream-cons x (merge xs yy))))))))
  (stream-let loop ((strms strms))
    (cond ((null? strms) stream-null)
          ((null? (cdr strms)) (car strms))
          (else (merge (car strms)
                       (apply stream-merge lt?
                         (cdr strms)))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>syntax: </b></font>
<font face="monospace"><b>(stream-of </b></font><font face="serif"><b><i>expr</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>clause</i></b></font><font face="monospace"><b> ...)</b></font><br>
<font face="monospace">Stream-of</font><font face="serif"> provides the syntax of stream comprehensions, 
which generate streams by means of looping expressions.  The result 
is a stream of objects of the type returned by <i>expr</i>.  There 
are four types of clauses:</font></font></font></p>

<ul type="disc">
<font face="serif"><font face="serif">  <li><font face="monospace">(</font><font face="serif"><i>var</i></font><font face="monospace"> in </font><font face="serif"><i>stream-expr</i></font><font face="monospace">)</font><font face="serif"> 
  &#8212; Loop over the elements of <i>stream-expr</i>, in order from the 
  start of the stream, binding each element of the stream in turn to <i>
  var</i>.  </font><font face="monospace">Stream-from</font><font face="serif"> and </font><font face="monospace">stream-range</font><font face="serif"> are frequently useful as generators 
  for <i>stream-expr</i>.</font></li>
  <li><font face="monospace">(</font><font face="serif"><i>var</i></font><font face="monospace"> is </font><font face="serif"><i>expr</i></font><font face="monospace">)</font><font face="serif"> 
  &#8212; Bind <i>var</i> to the value obtained by evaluating <i>expr</i>.</font></li>
  <li><font face="monospace">(pred? </font><font face="serif"><i>expr</i></font><font face="monospace">)</font><font face="serif"> 
  &#8212; Include in the output stream only those elements <i>x</i> for which </font><font face="monospace">(pred? </font><font face="serif"><i>x</i></font><font face="monospace">)</font><font face="serif"> 
  is non-</font><font face="monospace">#f</font><font face="serif">.</font></li>
</font></font></ul>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The scope of <i>
var</i>iables bound in the stream comprehension is the clauses to the 
right of the binding clause (but not the binding clause itself) plus 
the result expression.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">When two or 
more generators are present, the loops are processed as if they are 
nested from left to right; that is, the rightmost generator varies fastest.  
A consequence of this is that only the first generator may be infinite 
and all subsequent generators must be finite.  If no generators 
are present, the result of a stream comprehension is a stream containing 
the result expression; thus, </font><font face="monospace">(stream-of 
1)</font><font face="serif"> produces a finite stream 
containing only the element </font><font face="monospace">1</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-of (* x x)
  (x in (stream-range 0 10))
  (even? x))
  &#8658; 0 4 16 36 64</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-of (list a b)
  (a in (stream-range 1 4))
  (b in (stream-range 1 3))) 
  &#8658; (1 1) (1 2) (2 1) (2 2) (3 1) (3 2)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-of (list i j)
  (i in (stream-range 1 5))
  (j in (stream-range (+ i 1) 5)))
  &#8658; (1 2) (1 3) (1 4) (2 3) (2 4) (3 4)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-range </b></font><font face="serif"><b><i>first</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>past</i></b></font><font face="monospace"><b> 
[</b></font><font face="serif"><b><i>step</i></b></font><font face="monospace"><b>])</b></font><br>
<font face="monospace">number × number × number &#8594; {number}</font><br>
<font face="monospace">Stream-range</font><font face="serif"> creates a newly-allocated stream that 
contains <i>first</i> as its first element and increments each succeeding 
element by <i>step</i>.  The stream is finite and ends before <i>
past</i>, which is not an element of the stream.  If <i>step</i> 
is not given it defaults to </font><font face="monospace">1</font><font face="serif"> if <i>first</i> is less than <i>past</i> 
and </font><font face="monospace">-1</font><font face="serif"> 
otherwise.  <i>First</i>, <i>past</i> and <i>step</i> may be of 
any numeric type.  </font><font face="monospace">Stream-range</font><font face="serif"> is frequently useful as a generator 
in </font><font face="monospace">stream-of</font><font face="serif"> 
expressions.  See also </font><font face="monospace">stream-from</font><font face="serif"> for a similar procedure that creates 
infinite streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-range 0 
10) &#8658; 0 1 2 3 4 5 6 7 8 9</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-range 0 
10 2) &#8594; 0 2 4 6 8</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Successive 
elements of the stream are calculated by adding <i>step</i> to <i>first</i>, 
so if any of <i>first</i>, <i>past</i> or <i>step</i> are inexact, the 
length of the output stream may differ from </font><font face="monospace">(ceiling 
(- (/ (- </font><font face="serif"><i>past</i></font><font face="monospace"> </font><font face="serif"><i>first</i></font><font face="monospace">) </font><font face="serif"><i>step</i></font><font face="monospace">) 1)</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-ref </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>n</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">{&#945;} × nat &#8594; &#945;</font><br>
<font face="monospace">Stream-ref</font><font face="serif"> returns the <i>n</i>th element of <i>
stream</i>, counting from zero.  An error is signaled if <i>n</i> 
is greater than or equal to the length of <i>stream</i>.</font><font face="monospace"> </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (fact n)
  (stream-ref
    (stream-scan * 1 (stream-from 1))
    n))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-reverse </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">{&#945;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-reverse</font><font face="serif"> returns a newly-allocated stream containing 
the elements of the input <i>stream</i> but in reverse order.  </font><font face="monospace">Stream-reverse</font><font face="serif"> 
may only be used with finite streams; it enters an infinite loop with 
infinite streams.  </font><font face="monospace">Stream-reverse</font><font face="serif"> does not force evaluation of the elements 
of the stream.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>&gt; (define s (stream 1 (/ 1 0) -1))
&gt; (define r (stream-reverse s))
&gt; (stream-ref r 0)
&gt; (stream-ref r 2)
1
&gt; (stream-ref r 1)
error: division by zero</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-scan </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>base</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">(&#945; × &#946; &#8594; &#945;) × &#945; × {&#946;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-scan</font><font face="serif"> accumulates the partial folds of an 
input <i>stream</i> into a newly-allocated output stream.  The 
output stream is the <i>base</i> followed by </font><font face="monospace">(stream-fold 
proc base (stream-take </font><font face="serif"><i>i</i></font><font face="monospace"> stream))</font><font face="serif"> 
for each of the first <i>i</i> elements of <i>stream</i>.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-scan + 0 (stream-from 1))
  &#8658; (stream 0 1 3 6 10 15 ...)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-scan * 1 (stream-from 1))
  &#8658; (stream 1 1 2 6 24 120 ...)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-take </b></font><font face="serif"><b><i>n</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">nat × {&#945;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-take</font><font face="serif"> takes a non-negative integer <i>n</i> 
and a <i>stream</i> and returns a newly-allocated stream containing 
the first <i>n</i> elements of the input <i>stream</i>.  If the 
input <i>stream</i> has less than <i>n</i> elements, so does the output 
stream.  See also </font><font face="monospace">stream-drop</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Mergesort splits 
a stream into two equal-length pieces, sorts them recursively and merges 
the results:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (msort lt? strm)
  (let* ((n (quotient (stream-length strm) 2))
         (ts (stream-take n strm))
         (ds (stream-drop n strm)))
    (if (zero? n)
        strm
        (stream-merge lt?
          (msort &lt; ts) (msort &lt; ds)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-take-while </b></font><font face="serif"><b><i>pred?</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">(&#945; &#8594; boolean) × {&#945;} &#8594; {&#945;}</font><br>
<font face="monospace">Stream-take-while</font><font face="serif"> takes a predicate and a <i>stream</i> 
and returns a newly-allocated stream containing those elements <i>x</i> 
that form the maximal prefix of the input <i>stream</i> for which </font><font face="monospace">(pred? </font><font face="serif"><i>x</i></font><font face="monospace">)</font><font face="serif"> 
is non-</font><font face="monospace">#f</font><font face="serif">.  
See also </font><font face="monospace">stream-drop-while</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-car
  (stream-reverse
    (stream-take-while
      (lambda (x) (&lt; x 1000))
        primes))) &#8658; 997</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-unfold </b></font><font face="serif"><b><i>map</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>pred?</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>gen</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>base</i>)</b></font><br>
<font face="monospace">(&#945; &#8594; &#946;) × (&#945; &#8594; boolean) × (&#945; &#8594; &#945;) × &#945; &#8594; {&#946;}</font><br>
<font face="monospace">Stream-unfold</font><font face="serif"> is the fundamental recursive stream 
constructor.  It constructs a stream by repeatedly applying <i>
gen</i> to successive values of <i>base</i>, in the manner of </font><font face="monospace">stream-iterate</font><font face="serif">, 
then applying <i>map</i> to each of the values so generated, appending 
each of the mapped values to the output stream as long as </font><font face="monospace">(</font><font face="serif"><i>pred?</i></font><font face="monospace"> </font><font face="serif"><i>base</i></font><font face="monospace">)</font><font face="serif"> 
is non-</font><font face="monospace">#f</font><font face="serif">.  
See also </font><font face="monospace">stream-iterate</font><font face="serif"> and </font><font face="monospace">stream-unfolds</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The expression 
below creates the finite stream </font><font face="monospace">0</font><font face="serif"> </font><font face="monospace">1</font><font face="serif"> </font><font face="monospace">4</font><font face="serif"> </font><font face="monospace">9</font><font face="serif"> </font><font face="monospace">16</font><font face="serif"> </font><font face="monospace">25</font><font face="serif"> </font><font face="monospace">36</font><font face="serif"> </font><font face="monospace">49</font><font face="serif"> </font><font face="monospace">64</font><font face="serif"> </font><font face="monospace">81</font><font face="serif">.  Initially the </font><font face="monospace">base</font><font face="serif"> is </font><font face="monospace">0</font><font face="serif">, which is less than </font><font face="monospace">10</font><font face="serif">, so <i>map</i> squares the <i>base</i> 
and the mapped value becomes the first element of the output stream.  
Then <i>gen</i> increments the <i>base</i> by </font><font face="monospace">1</font><font face="serif">, so it becomes </font><font face="monospace">1</font><font face="serif">; this is less than </font><font face="monospace">10</font><font face="serif">, so <i>map</i> squares the new </font><font face="monospace">base</font><font face="serif"> 
and </font><font face="monospace">1</font><font face="serif"> 
becomes the second element of the output stream.  And so on, until 
the <i>base</i> becomes </font><font face="monospace">10</font><font face="serif">, when <i>pred?</i> stops the recursion 
and </font><font face="monospace">stream-null</font><font face="serif"> ends the output stream.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-unfold
  (lambda (x) (expt x 2)) ; map
  (lambda (x) (&lt; x 10))   ; pred?
  (lambda (x) (+ x 1))    ; gen
  0)                      ; base</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-unfolds </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>seed</i></b></font><font face="monospace"><b>)</b></font><br>
<font face="monospace">(&#945; &#8594; (values &#945; × &#946; ...)) × &#945; &#8594; (values {&#946;} ...)</font><br>
<font face="monospace">Stream-unfolds</font><font face="serif"> returns <i>n</i> newly-allocated streams 
containing those elements produced by successive calls to the generator <i>
proc</i>, which takes the current <i>seed</i> as its argument and returns <i>
n</i></font><font face="monospace">+1</font><font face="serif"> 
values</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(</font><font face="serif"><i>proc</i></font><font face="monospace"> </font><font face="serif"><i>seed</i></font> &#8594; <font face="serif"><i>seed</i></font><font face="monospace"> </font><font face="serif"><i>result</i><sub><i>0</i></sub></font><font face="monospace"> ... </font><font face="serif"><i>result</i><sub><i>n-1</i></sub></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">where the returned <i>
seed</i> is the input <i>seed</i> to the next call to the generator 
and <i>result</i><sub><i>i</i></sub> indicates how to produce the next 
element of the <i>i</i><sup><i>th</i></sup> result stream:</font></font></font></p>

<ul type="disc">
<font face="serif"><font face="serif">  <li><font face="monospace">(</font><font face="serif"><i>value</i></font><font face="monospace">)</font><font face="serif"> 
  &#8212; <i>value</i> is the next car of the result stream</font></li>
  <li><font face="monospace">#f</font><font face="serif"> 
  &#8212; no value produced by this iteration of the generator <i>proc</i> 
  for the result stream</font></li>
  <li><font face="monospace">()</font><font face="serif"> 
  &#8212; the end of the result stream</font></li>
</font></font></ul>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">It may require 
multiple calls of <i>proc</i> to produce the next element of any particular 
result stream.  See also </font><font face="monospace">stream-iterate</font><font face="serif"> and </font><font face="monospace">stream-unfold</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-unfolds</font><font face="serif"> is especially useful when writing 
expressions that return multiple streams.  For instance, </font><font face="monospace">(stream-partition </font><font face="serif"><i>pred?</i></font><font face="monospace"> </font><font face="serif"><i>strm</i></font><font face="monospace">)</font><font face="serif"> 
is equivalent to</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(values
  (stream-filter </font><font face="serif"><i>pred?</i></font><font face="monospace"> </font><font face="serif"><i>strm</i></font><font face="monospace">)
  (stream-filter
    (lambda (x) (not (</font><font face="serif"><i>pred?</i></font><font face="monospace"> x))) </font><font face="serif"><i>strm</i></font><font face="monospace">))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">but only tests <i>
pred?</i> once for each element of <i>strm</i>.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-partition pred? strm)
  (stream-unfolds
    (lambda (s)
      (if (stream-null? s)
          (values s '() '())
          (let ((a (stream-car s))
                (d (stream-cdr s)))
            (if (pred? a)
                (values d (list a) #f)
                (values d #f (list a))))))
    strm))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(call-with-values
  (lambda ()
    (stream-partition odd?
      (stream-range 1 6)))
  (lambda (odds evens)
    (list (stream-&gt;list odds)
          (stream-&gt;list evens))))
  &#8658; ((1 3 5) (2 4))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><b>procedure: </b></font>
<font face="monospace"><b>(stream-zip </b></font><font face="serif"><b><i>stream</i></b></font><font face="monospace"><b> ...)</b></font><br>
<font face="monospace">{&#945;} × {&#946;} × ... &#8594; {[&#945; &#946; ...]}</font><br>
<font face="monospace">Stream-zip</font><font face="serif"> takes one or more input <i>stream</i>s 
and returns a newly-allocated stream in which each element is a list 
(not a stream) of the corresponding elements of the input <i>stream</i>s.  
The output stream is as long as the shortest input <i>stream</i>, if 
any of the input <i>stream</i>s is finite, or is infinite if all the 
input <i>stream</i>s are infinite.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">A common use 
of </font><font face="monospace">stream-zip</font><font face="serif"> 
is to add an index to a stream, as in </font><font face="monospace">(stream-finds </font><font face="serif"><i>eql?</i></font><font face="monospace"> </font><font face="serif"><i>obj</i></font><font face="monospace"> </font><font face="serif"><i>strm</i></font><font face="monospace">)</font><font face="serif">, which returns all the zero-based 
indices in <i>strm</i> at which <i>obj</i> appears; </font><font face="monospace">(stream-find </font><font face="serif"><i>eql?</i></font><font face="monospace"> </font><font face="serif"><i>obj</i></font><font face="monospace"> </font><font face="serif"><i>strm</i></font><font face="monospace">)</font><font face="serif"> returns the first such index, or </font><font face="monospace">#f</font><font face="serif"> 
if <i>obj</i> is not in <i>strm</i>.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-finds eql? obj strm)
  (stream-of (car x)
    (x in (stream-zip (stream-from 0) strm))
    (eql? obj (cadr x))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-find eql? obj strm)
  (stream-car
    (stream-append
      (stream-finds eql? obj strm)
      (stream #f))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-find char=? #\l
  (list-&gt;stream
    (string-&gt;list "hello"))) &#8658; 2</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-find char=? #\l
  (list-&gt;stream
    (string-&gt;list "goodbye"))) &#8658; #f</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Stream-find</font><font face="serif"> is not as inefficient as it looks; 
although it calls </font><font face="monospace">stream-finds</font><font face="serif">, which finds all matching indices, 
the matches are computed lazily, and only the first match is needed 
for </font><font face="monospace">stream-find</font><font face="serif">.</font></font></font></p>

<h1><font face="serif"><font face="serif">Utilities</font></font></h1>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Streams, being 
the signature structured data type of functional programming languages, 
find useful expression in conjunction with higher-order functions.  
Some of these higher-order functions, and their relationship to streams, 
are described below.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The identity 
and constant procedures are frequently useful as the recursive base 
for maps and folds; </font><font face="monospace"><b>(identity </b></font><font face="serif"><b><i>obj</i></b></font><font face="monospace"><b>)</b></font><font face="serif"> always returns <i>obj</i>, and </font><font face="monospace"><b>(const </b></font><font face="serif"><b><i>obj</i></b></font><font face="monospace"><b>)</b></font><font face="serif"> 
creates a procedure that takes any number of arguments and always returns 
the same <i>obj</i>, no matter its arguments:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define (identity 
obj) obj)</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define (const 
obj) (lambda x obj))</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Many of the 
stream procedures take a unary predicate that accepts an element of 
a stream and returns a boolean.  Procedure </font><font face="monospace"><b>(negate </b></font><font face="serif"><b><i>pred?</i></b></font><font face="monospace"><b>)</b></font><font face="serif"> takes a unary predicate and returns 
a new unary predicate that, when called, returns the opposite boolean 
value as the original predicate.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (negate pred?)
  (lambda (x) (not (pred? x))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Negate</font><font face="serif"> is useful for procedures like </font><font face="monospace">stream-take-while</font><font face="serif"> 
that take a predicate, allowing them to be used in the opposite direction 
from which they were written; for instance, with the predicate reversed, </font><font face="monospace">stream-take-while</font><font face="serif"> 
becomes </font><font face="monospace">stream-take-until</font><font face="serif">.  </font><font face="monospace">Stream-remove</font><font face="serif"> is the opposite of </font><font face="monospace">stream-filter</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-remove pred? strm)
  (stream-filter (negate pred?) strm))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">A section is 
a procedure which has been partially applied to some of its arguments; 
for instance, </font><font face="monospace">(double </font><font face="serif"><i>x</i></font><font face="monospace">)</font><font face="serif">, which returns twice its argument, 
is a partial application of the multiply operator to the number </font><font face="monospace">2</font><font face="serif">.  
Sections come in two kinds: left sections partially apply arguments 
starting from the left, and right sections partially apply arguments 
starting from the right.  Procedure </font><font face="monospace"><b>(lsec </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>args</i></b></font><font face="monospace"><b> 
...)</b></font><font face="serif"> takes a <i>proc</i>edure 
and some prefix of its arguments and returns a new procedure in which 
those arguments are partially applied.  Procedure </font><font face="monospace"><b>(rsec </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> </b></font><font face="serif"><b><i>args</i></b></font><font face="monospace"><b> 
...)</b></font><font face="serif"> takes a <i>proc</i>edure 
and some reversed suffix of its arguments and returns a new procedure 
in which those arguments are partially applied.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (lsec proc . args)
  (lambda x (apply proc (append args x))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (rsec proc . args)
  (lambda x (apply proc (reverse
    (append (reverse args) (reverse x))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Since most 
of the stream procedures take a stream as their last (right-most) argument, 
left sections are particularly useful in conjunction with streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define stream-sum 
(lsec stream-fold + 0))</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Function composition 
creates a new function by partially applying multiple functions, one 
after the other.  In the simplest case there are only two functions, </font><font face="monospace">f</font><font face="serif"> 
and </font><font face="monospace">g</font><font face="serif">, 
composed as </font><font face="monospace">((compose f g) &#8801; <i>x</i></font><font face="monospace">))</font><font face="serif">; 
the composition can be bound to create a new function, as in </font><font face="monospace">(define fg (compose f g))</font><font face="serif">.  
Procedure </font><font face="monospace"><b>(compose </b></font><font face="serif"><b><i>proc</i></b></font><font face="monospace"><b> 
...)</b></font><font face="serif"> takes one or more <i>
proc</i>edures and returns a new procedure that performs the same action 
as the individual procedures would if called in succession.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (compose . fns)
  (let comp ((fns fns))
    (cond
      ((null? fns) 'error)
      ((null? (cdr fns)) (car fns))
      (else
        (lambda args
          (call-with-values
            (lambda ()
              (apply
                (comp (cdr fns))
                args))
            (car fns)))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Compose</font><font face="serif"> works with sections to create succinct 
but highly expressive procedure definitions.  The expression to 
compute the squares of the integers from </font><font face="monospace">1</font><font face="serif"> to </font><font face="monospace">10</font><font face="serif"> given above at </font><font face="monospace">stream-unfold</font><font face="serif"> could be written by composing </font><font face="monospace">stream-map</font><font face="serif">, </font><font face="monospace">stream-take-while</font><font face="serif">, 
and </font><font face="monospace">stream-iterate</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>((compose
  (lsec stream-map (rsec expt 2))
  (lsec stream-take-while (negate (rsec &gt; 10)))
  (lsec stream-iterate (rsec + 1)))
 1)</pre></font></font></font></p>

<h1><font face="serif"><font face="serif">Examples</font></font></h1>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The examples 
below show a few of the myriad ways streams can be exploited, as well 
as a few ways they can trip the unwary user.  All the examples 
are drawn from published sources; it is instructive to compare the Scheme 
versions to the originals in other languages.</font></font></font></p>

<h2><font face="serif"><font face="serif">Infinite streams</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">As a simple 
illustration of infinite streams, consider this definition of the natural 
numbers:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define nats
  (stream-cons 0
    (stream-map add1 nats)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The recursion 
works because it is offset by one from the initial </font><font face="monospace">stream-cons</font><font face="serif">.  Another sequence that uses 
the offset trick is this definition of the fibonacci numbers:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define fibs
  (stream-cons 1
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Yet another 
sequence that uses the same offset trick is the Hamming numbers, named 
for the mathematician and computer scientist Richard Hamming, defined 
as all numbers that have no prime factors greater than 5; in other words, 
Hamming numbers are all numbers expressible as 2<sup><i>i</i></sup>·3<sup><i>j</i></sup>·5<sup><i>k</i></sup>, 
where <i>i</i>, <i>j</i> and <i>k</i> are non-negative integers.  The 
Hamming sequence starts with </font><font face="monospace">1 
2 3 4 5 6 8 9 10 12</font><font face="serif"> and 
is computed starting with </font><font face="monospace">1</font><font face="serif">, taking </font><font face="monospace">2</font><font face="serif">, </font><font face="monospace">3</font><font face="serif"> and </font><font face="monospace">5</font><font face="serif"> times all the previous elements with </font><font face="monospace">stream-map</font><font face="serif">, 
then merging sub-streams and eliminating duplicates.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define hamming
  (stream-cons 1
    (stream-unique =
      (stream-merge &lt;
        (stream-map (lsec * 2) hamming)
        (stream-map (lsec * 3) hamming)
        (stream-map (lsec * 5) hamming)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">It is possible 
to have an infinite stream of infinite streams.  Consider the definition 
of </font><font face="monospace">power-table</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define power-table
  (stream-of
    (stream-of (expt m n)
      (m in (stream-from 1)))
      (n in (stream-from 2))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">which evaluates 
to an infinite stream of infinite streams:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><mpre>
(stream
  (stream 1 4 9 16 25 ...)
  (stream 1 8 27 64 125 ...)
  (stream 1 16 81 256 625 ...)
  ...)</mpre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">But even though 
it is impossible to display </font><font face="monospace">power-table</font><font face="serif"> in its entirety, it is possible to 
select just part of it:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-&gt;list 10 (stream-ref power-table 1))
  &#8658; (1 8 27 64 125 216 343 512 729 1000)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">This example 
clearly shows that the elements of a stream are computed lazily, as 
they are needed; </font><font face="monospace">(stream-ref 
power-table 0)</font><font face="serif"> is not computed, 
even when its successor is displayed, since computing it would enter 
an infinite loop.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Chris Reade 
shows how to calculate the stream of prime numbers according to the 
sieve of Eratosthenes, using a method that eliminates multiples of the 
sifting base with addition rather than division:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define primes (let ()
  (define-stream (next base mult strm)
    (let ((first (stream-car strm))
          (rest (stream-cdr strm)))
      (cond ((&lt; first mult)
              (stream-cons first
                (next base mult rest)))
            ((&lt; mult first)
              (next base (+ base mult) strm))
            (else (next base
                    (+ base mult) rest)))))
  (define-stream (sift base strm)
    (next base (+ base base) strm))
  (define-stream (sieve strm)
    (let ((first (stream-car strm))&gt;
          (rest (stream-cdr strm)))
      (stream-cons first
        (sieve (sift first rest)))))
  (sieve (stream-from 2))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">A final example 
of infinite streams is a functional pearl from Jeremy Gibbons, David 
Lester and Richard Bird that enumerates the positive rational numbers 
without duplicates:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define rats
  (stream-iterate
    (lambda (x)
      (let* ((n (floor x)) (y (- x n)))
        (/ (- n -1 y))))
    1))</pre></font></font></font></p>

<h2><font face="serif"><font face="serif">Backtracking via the stream of successes</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Philip Wadler 
describes the <i>stream of successes</i> technique that uses streams 
to perform backtracking search.   The basic idea is that each procedure 
returns a stream of possible results, so that its caller can decide 
which result it wants; an empty stream signals failure, and causes backtracking 
to a previous choice point.  The stream of successes technique 
is useful because the program is written as if to simply enumerate all 
possible solutions; no backtracking is explicit in the code.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The Eight Queens 
puzzle, which asks for a placement of eight queens on a chessboard so 
that none of them attack any other, is an example of a problem that 
can be solved using the stream of successes technique.  The algorithm 
is to place a queen in the first column of a chessboard; any column 
is satisfactory.  Then a queen is placed in the second column, 
in any position not held in check by the queen in the first column.  
Then a queen is placed in the third column, in any position not held 
in check by the queens in the first two columns.  And so on, until 
all eight queens have been placed.  If at any point there is no 
legal placement for the next queen, backtrack to a different legal position 
for the previous queens, and try again.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The chessboard 
is represented as a stream of length <i>m</i>, where there are queens 
in the first <i>m</i> columns, each position in the stream representing 
the rank on which the queen appears in that column.  For example, 
stream </font><font face="monospace">4</font><font face="serif"> </font><font face="monospace">6</font><font face="serif"> </font><font face="monospace">1</font><font face="serif"> </font><font face="monospace">5</font><font face="serif"> </font><font face="monospace">2</font><font face="serif"> </font><font face="monospace">8</font><font face="serif"> </font><font face="monospace">3</font><font face="serif"> </font><font face="monospace">7</font><font face="serif"> 
represents the following chessboard:</font></font></font></p>

<p align="center"><font face="serif"><font face="serif"><img src="srfi-41_files/streams2.jpg" alt="Chessboard" height="205" width="195"></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Two queens 
at column <i>i</i> row <i>j</i> and column <i>m</i> row <i>n</i> check 
each other if their columns <i>i</i> and <i>m</i> are the same, or if 
their rows <i>j</i> and <i>n</i> are the same, or if they are on the 
same diagonal with <i>i</i> + <i>j</i> = <i>m</i> + <i>n</i> or <i>i</i> 
&#8211; <i>j</i> = <i>m</i> &#8211; <i>n</i>.  There is no need to test 
the columns, because the placement algorithm enforces that they differ, 
so the </font><font face="monospace">check?</font><font face="serif"> 
procedure tests if two queens hold each other in check.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (check? i j m n)
  (or (= j n)
      (= (+ i j) (+ m n))
      (= (- i j) (- m n))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The algorithm 
walks through the columns, extending position <i>p</i> by adding a new 
queen in row <i>n</i> with </font><font face="monospace">(stream-append </font><font face="serif"><i>p</i></font><font face="monospace"> 
(stream </font><font face="serif"><i>n</i></font><font face="monospace">))</font><font face="serif">.  </font><font face="monospace">Safe?</font><font face="serif"> 
tests if it is safe to do so, using the utility procedure </font><font face="monospace">stream-and</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-and strm)
  (let loop ((strm strm))
    (cond ((stream-null? strm) #t)
          ((not (stream-car strm)) #f)
          (else (loop (stream-cdr strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (safe? p n)
  (let* ((len (stream-length p))
         (m (+ len 1)))
    (stream-and
      (stream-of
        (not (check? (car ij) (cadr ij) m n))
          (ij in (stream-zip
                   (stream-range 1 m)
                   p))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Procedure </font><font face="monospace">(queens </font><font face="serif"><i>m</i></font><font face="monospace">)</font><font face="serif"> 
returns all the ways that queens can safely be placed in the first <i>
m</i> columns.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queens m)
  (if (zero? m)
      (stream (stream))
      (stream-of (stream-append p (stream n))
        (p in (queens (- m 1)))
        (n in (stream-range 1 9))
        (safe? p n))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">To see the 
first solution to the Eight Queens problem, say</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(stream-&gt;list 
(stream-car (queens 8)))</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">To see all 
92 solutions, say</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-&gt;list
  (stream-map stream-&gt;list
    (queens 8)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">There is no 
explicit backtracking in the code.  The </font><font face="monospace">stream-of</font><font face="serif"> expression in </font><font face="monospace">queens</font><font face="serif"> returns all possible streams that 
satisfy </font><font face="monospace">safe?</font><font face="serif">; 
implicit backtracking occurs in the recursive call to </font><font face="monospace">queens</font><font face="serif">.</font></font></font></p>

<h2><font face="serif"><font face="serif">Generators and co-routines</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">It is possible 
to model generators and co-routines using streams.  Consider the task, 
due to Carl Hewitt, of determining if two trees have the same sequence 
of leaves:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(same-fringe? = 
'(1 (2 3)) '((1 2) 3)) &#8658; #t</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(same-fringe? = 
'(1 2 3) '(1 (3 2))) &#8658; #f</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The simplest 
solution is to flatten both trees into lists and compare them element-by-element:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (flatten tree)
  (cond ((null? tree) '())
        ((pair? (car tree))
          (append (flatten (car tree))
                  (flatten (cdr tree))))
        (else (cons (car tree)
                    (flatten (cdr tree))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (same-fringe? eql? tree1 tree2)
  (let loop ((t1 (flatten tree1))
             (t2 (flatten tree2)))
    (cond ((and (null? t1) (null? t2)) #t)
          ((or (null? t1) (null? t2)) #f)
          ((not (eql? (car t1) (car t2))) #f)
          (else (loop (cdr t1) (cdr t2))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">That works, 
but requires time to flatten both trees and space to store the flattened 
versions; if the trees are large, that can be a lot of time and space, 
and if the fringes differ, much of that time and space is wasted.</font></font></font></p>
<p align="justify"><font face="serif"><font face="serif"><font face="serif">Hewitt used 
a generator to flatten the trees one element at a time, storing only 
the current elements of the trees and the machines needed to continue 
flattening them, so </font><font face="monospace">same-fringe?</font><font face="serif"> could stop early if the trees differ.  
Dorai Sitaram presents both the generator solution and a co-routine 
solution, which both involve tricky calls to </font><font face="monospace">call-with-current-continuation</font><font face="serif"> and careful coding to keep them synchronized.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">An alternate 
solution flattens the two trees to streams instead of lists, which accomplishes 
the same savings of time and space, and involves code that looks little 
different than the list solution presented above:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (flatten tree)
  (cond ((null? tree) stream-null)
        ((pair? (car tree))
          (stream-append
            (flatten (car tree))
            (flatten (cdr tree))))
        (else (stream-cons
                (car tree)
                (flatten (cdr tree))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (same-fringe? eql? tree1 tree2)
  (let loop ((t1 (flatten tree1))
             (t2 (flatten tree2)))
    (cond ((and (stream-null? t1)
                (stream-null? t2)) #t)
          ((or  (stream-null? t1)
                (stream-null? t2)) #f)
          ((not (eql? (stream-car t1)
                      (stream-car t2))) #f)
          (else (loop (stream-cdr t1)
                      (stream-cdr t2))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Note that streams, 
a data structure, replace generators or co-routines, which are control 
structures, providing a fine example of how lazy streams enhance modularity.</font></font></font></p>

<h2><font face="serif"><font face="serif">A pipeline of procedures</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Another way 
in which streams promote modularity is enabling the use of many small 
procedures that are easily composed into larger programs, in the style 
of unix pipelines, where streams are important because they allow a 
large dataset to be processed one item at a time.  Bird and Wadler 
provide the example of a text formatter.  Their example uses right-folds:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-fold-right f base strm) 
  (if (stream-null? strm)
      base
      (f (stream-car strm)
         (stream-fold-right f base
           (stream-cdr strm)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-fold-right-one f strm)
  (stream-match strm
  ((x) x)
  ((x . xs)
    (f x (stream-fold-right-one f xs)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Bird and Wadler 
define text as a stream of characters, and develop a standard package 
for operating on text, which they derive mathematically (this assumes 
the line-separator character is a single </font><font face="monospace">#\newline</font><font face="serif">):</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (breakon a)
  (stream-lambda (x xss)
    (if (equal? a x)
        (stream-append (stream (stream)) xss)
        (stream-append
          (stream (stream-append
              (stream x) (stream-car xss)))
          (stream-cdr xss)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (lines strm) 
  (stream-fold-right
    (breakon #\newline)
    (stream (stream))
    strm))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (words strm)
  (stream-filter stream-pair?
    (stream-fold-right
      (breakon #\space)
      (stream (stream))
      strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (paras strm)
  (stream-filter stream-pair?
    (stream-fold-right
      (breakon stream-null)
      (stream (stream))
      strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (insert a)
  (stream-lambda (xs ys)
    (stream-append xs (stream a) ys)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define unlines
  (lsec stream-fold-right-one
    (insert #\newline)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define unwords
  (lsec stream-fold-right-one
    (insert #\space)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define unparas
  (lsec stream-fold-right-one
    (insert stream-null)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">These versatile 
procedures can be composed to count words, lines and paragraphs; the </font><font face="monospace">normalize</font><font face="serif"> 
procedure squeezes out multiple spaces and blank lines:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define countlines
  (compose stream-length lines))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define countwords
  (compose stream-length
           stream-concat
           (lsec stream-map words)
           lines))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define countparas
  (compose stream-length paras lines))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define parse
  (compose (lsec stream-map
             (lsec stream-map words))
           paras
           lines))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define unparse
  (compose unlines
           unparas
           (lsec stream-map
             (lsec stream-map unwords))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define normalize (compose unparse parse))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">More useful 
than normalization is text-filling, which packs as many words onto each 
line as will fit.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (greedy m ws)
  (- (stream-length
       (stream-take-while (rsec &lt;= m)
         (stream-scan
           (lambda (n word)
             (+ n (stream-length word) 1))
           -1
           ws))) 1))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (fill m ws)
  (if (stream-null? ws)
      stream-null
      (let* ((n (greedy m ws))
             (fstline (stream-take n ws))
             (rstwrds (stream-drop n ws)))
        (stream-append
          (stream fstline)
          (fill m rstwrds)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define linewords
  (compose stream-concat
           (lsec stream-map words)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define textparas
  (compose (lsec stream-map linewords)
           paras
           lines))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (filltext m strm)
  (unparse (stream-map (lsec fill m) (textparas strm))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">To display <i>
filename</i> in lines of <i>n</i> characters, say:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(stream-for-each display
  (filltext </font><font face="serif"><i>n</i></font><font face="monospace"> (file-&gt;stream </font><font face="serif"><i>filename</i></font><font face="monospace">)))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Though each 
operator performs only a single task, they can be composed powerfully 
and expressively.  The alternative is to build a single monolithic 
procedure for each task, which would be harder and involve repetitive 
code.  Streams ensure procedures are called as needed.</font></font></font></p>

<h2><font face="serif"><font face="serif">Persistent data</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Queues are 
one of the fundamental data structures of computer science.  In 
functional languages, queues are commonly implemented using two lists, 
with the front half of the queue in one list, where the head of the 
queue can be accessed easily, and the rear half of the queue in reverse 
order in another list, where new items can easily be added to the end 
of a queue.  The standard form of such a queue holds that the front 
list can only be null if the rear list is also null: </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(define queue-null (cons '() '())</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-null? obj)
  (and (pair? obj) (null? (car obj))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-check f r)
  (if (null? f)
      (cons (reverse r) '())
      (cons f r)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-snoc q x)
  (queue-check (car q) (cons x (cdr q))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-head q)
  (if (null? (car q))
      (error "empty queue: head")
      (car (car q))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-tail q)
  (if (null? (car q))
      (error "empty-head: tail")
      (queue-check (cdr (car q)) (cdr q))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">This queue 
operates in amortized constant time per operation, with two conses per 
element, one when it is added to the rear list, and another when the 
rear list is reversed to become the front list.  </font><font face="monospace">Queue-snoc</font><font face="serif"> and </font><font face="monospace">queue-head</font><font face="serif"> operate in constant time; </font><font face="monospace">queue-tail</font><font face="serif"> 
operates in worst-case linear time when the front list is empty.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Chris Okasaki 
points out that, if the queue is used persistently, its time-complexity 
rises from linear to quadratic since each persistent copy of the queue 
requires its own linear-time access.  The problem can be fixed 
by implementing the front and rear parts of the queue as streams, rather 
than lists, and rotating one element from rear to front whenever the 
rear list is larger than the front list: </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define queue-null
  (cons stream-null stream-null))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-null? x)
  (and (pair? x) (stream-null (car x))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-check f r)
  (if (&lt; (stream-length r) (stream-length f))
      (cons f r)
      (cons (stream-append f (stream-reverse r))
            stream-null)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-snoc q x)
  (queue-check (car q) (stream-cons x (cdr q))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-head q)
  (if (stream-null? (car q))
      (error "empty queue: head")
      (stream-car (car q))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (queue-tail q)
  (if (stream-null? (car q))
      (error "empty queue: tail")
      (queue-check (stream-cdr (car q))
                   (cdr q))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Memoization 
solves the persistence problem; once a queue element has moved from 
rear to front, it need never be moved again in subsequent traversals 
of the queue.  Thus, the linear time-complexity to access all elements 
in the queue, persistently, is restored. </font></font></font></p>

<h2><font face="serif"><font face="serif">Reducing two passes to one</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The final example 
is a lazy dictionary, where definitions and uses may occur in any order; 
in particular, uses may precede their corresponding definitions.  
This is a common problem.  Many programming languages allow procedures 
to be used before they are defined.  Macro processors must collect 
definitions and emit uses of text in order.  An assembler needs 
to know the address that a linker will subsequently give to variables.  
The usual method is to make two passes over the data, collecting the 
definitions on the first pass and emitting the uses on the second pass.  
But Chris Reade shows how streams allow the dictionary to be built lazily, 
so that only a single pass is needed.  Consider a stream of requests:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define requests
  (stream
    '(get 3)
    '(put 1 "a")    ; use follows definition
    '(put 3 "c")    ; use precedes definition
    '(get 1)
    '(get 2)
    '(put 2 "b")    ; use precedes definition
    '(put 4 "d")))  ; unused definition</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">We want a procedure 
that will display </font><font face="monospace">cab</font><font face="serif">, which is the result of </font><font face="monospace">(get 3)</font><font face="serif">, </font><font face="monospace">(get 1)</font><font face="serif">, 
and </font><font face="monospace">(get 2)</font><font face="serif">, 
in order.  We first separate the request stream into </font><font face="monospace">gets</font><font face="serif"> 
and </font><font face="monospace">puts</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (get? obj) (eq? (car obj) 'get))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (gets strm)
  (stream-map cadr (stream-filter get? strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (puts strm)
  (stream-map cdr  (stream-remove get? strm)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Now, </font><font face="monospace">run-dict</font><font face="serif"> 
inserts each element of the </font><font face="monospace">puts</font><font face="serif"> stream into a lazy dictionary, represented 
as a stream of key/value pairs (an association stream), then looks up 
each element of the </font><font face="monospace">gets</font><font face="serif"> stream with </font><font face="monospace">stream-assoc</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (run-dict requests)
  (let ((dict (build-dict (puts requests))))
    (stream-map (rsec stream-assoc dict)
      (gets requests))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-assoc key dict)
    (cond ((stream-null? dict) #f)
          ((equal? key (car (stream-car dict)))
            (stream-car dict))
          (else (stream-assoc key
                  (stream-cdr dict)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">Dict</font><font face="serif"> is created in the </font><font face="monospace">let</font><font face="serif">, but nothing is initially added to 
it.  Each time </font><font face="monospace">stream-assoc</font><font face="serif"> performs a lookup, enough of </font><font face="monospace">dict</font><font face="serif"> 
is built to satisfy the lookup, but no more.  We are assuming that 
each item is defined once and only once.  All that is left is to 
define the procedure that inserts new items into the dictionary, lazily:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (build-dict puts)
  (if (stream-null? puts)
      stream-null
      (stream-cons
        (stream-car puts)
        (build-dict (stream-cdr puts)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Now we can 
run the requests and print the result:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-for-each display
  (stream-map cadr (run-dict requests)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The </font><font face="monospace">(put 4 "d")</font><font face="serif"> 
definition is never added to the dictionary because it is never needed.</font></font></font></p>

<h2><font face="serif"><font face="serif">Pitfalls</font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Programming 
with streams, or any lazy evaluator, can be tricky, even for programmers 
experienced in the genre.  Programming with streams is even worse 
in Scheme than in a purely functional language, because, though the 
streams are lazy, the surrounding Scheme expressions in which they are 
embedded are eager.  The impedance between lazy and eager can occasionally 
lead to astonishing results.  Thirty-two years ago, William Burge 
warned:</font></font></font></p>

<ul><p align="justify"><font face="serif"><font face="serif"><font face="serif">Some care 
must be taken when a stream is produced to make sure that its elements 
are not really a list in disguise, in other words, to make sure that 
the stream elements are not materialized too soon.</font></font></font></p></ul>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">For example, 
a simple version of </font><font face="monospace">stream-map</font><font face="serif"> that returns a stream built by applying 
a unary procedure to the elements of an input stream could be defined 
like this:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-map proc strm) ;wrong!
  (let loop ((strm strm))
    (if (stream-null? strm)
        stream-null
        (stream-cons
          (proc (stream-car strm))
          (loop (stream-cdr strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">That looks 
right.  It properly wraps the procedure in </font><font face="monospace">stream-lambda</font><font face="serif">, and the two legs of the </font><font face="monospace">if</font><font face="serif"> 
both return streams, so it type-checks.  But it fails because the 
named </font><font face="monospace">let</font><font face="serif"> 
binds </font><font face="monospace">loop</font><font face="serif"> 
to a procedure using normal </font><font face="monospace">lambda</font><font face="serif"> rather than </font><font face="monospace">stream-lambda</font><font face="serif">, so even though the first element 
of the result stream is lazy, subsequent elements are eager.  </font><font face="monospace">Stream-map</font><font face="serif"> 
can be written using </font><font face="monospace">stream-let</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-map proc strm)
  (stream-let loop ((strm strm))
    (if (stream-null? strm)
        stream-null
        (stream-cons
          (proc (stream-car strm))
          (loop (stream-cdr strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Here, </font><font face="monospace">stream-let</font><font face="serif"> 
assures that each element of the result stream is properly delayed, 
because each is subject to the </font><font face="monospace">stream-lambda</font><font face="serif"> that is implicit in </font><font face="monospace">stream-let</font><font face="serif">, so the result is truly a stream, 
not a &#8220;list in disguise.&#8221;  Another version of this procedure 
was given previously at the description of </font><font face="monospace">define-stream</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Another common 
problem occurs when a stream-valued procedure requires the next stream 
element in its definition.  Consider this definition of </font><font face="monospace">stream-unique</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define-stream (stream-unique eql? strm) ;wrong!
  (stream-match strm
    (() strm)
    ((_) strm)
    ((a b . _)
      (if (eql? a b)
          (stream-unique eql?
            (stream-cdr strm))
          (stream-cons a
            (stream-unique eql?
              (stream-cdr strm)))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The </font><font face="monospace">(a b . _)</font><font face="serif"> 
pattern requires the value of the next stream element after the one 
being considered.  Thus, to compute the <i>n</i><sup>th</sup> element 
of the stream, one must know the <i>n</i>+1<sup>st</sup> element, and 
to compute the <i>n</i>+1<sup>st</sup> element, one must know the <i>
n</i>+2<sup>nd</sup> element, and to compute&#8230;.  The correct version, 
given above in the description of </font><font face="monospace">stream-drop-while</font><font face="serif">, only needs the current stream element.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">A similar problem 
occurs when the stream expression uses the previous element to compute 
the current element:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">(define (nat n)
  (stream-ref
    (stream-let loop ((s (stream 0)))
      (stream-cons (stream-car s)
        (loop (stream (add1 (stream-car s))))))
    n))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">This program 
traverses the stream of natural numbers, building the stream as it goes.  
The definition is correct; </font><font face="monospace">(nat 
15)</font><font face="serif"> evaluates to </font><font face="monospace">15</font><font face="serif">.  
But it needlessly uses unbounded space because each stream element holds 
the value of the prior stream element in the binding to </font><font face="monospace">s</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">When traversing 
a stream, it is easy to write the expression in such a way that evaluation 
requires unbounded space, even when that is not strictly necessary.  
During the discussion of SRFI-40, Joe Marshall created this infamous 
procedure:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (times3 n)
  (stream-ref
    (stream-filter
      (lambda (x)
        (zero? (modulo x n)))
      (stream-from 0))
    3))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(times3 5)</font><font face="serif"> evaluates to </font><font face="monospace">15</font><font face="serif"> and </font><font face="monospace">(times3 
#e1e9)</font><font face="serif"> evaluates to three 
billion, though it takes a while.  In either case, </font><font face="monospace">times3</font><font face="serif"> 
should operate in bounded space, since each iteration mutates the promise 
that holds the next value.  But it is easy to write </font><font face="monospace">times3</font><font face="serif"> 
so that it does not operate in bounded space, as the follies of SRFI-40 
showed.  The common problem is that some element of the stream 
(often the first element) is bound outside the expression that is computing 
the stream, so it holds the head of the stream, which holds the second 
element, and so on.  In addition to testing the programmer, this 
procedure tests the stream primitives (it caught several errors during 
development) and also tests the underlying Scheme system (it found a 
bug in one implementation).</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Laziness is 
no defense against an infinite loop; for instance, the expression below 
never returns, because the </font><font face="monospace">odd?</font><font face="serif"> predicate never finds an odd stream 
element.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-null?
  (stream-filter odd?
    (stream-from 0 2)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Ultimately, 
streams are defined as promises, which are implemented as thunks (lambda 
with no arguments).  Since a stream is a procedure, comparisons 
such as </font><font face="monospace">eq?</font><font face="serif">, </font><font face="monospace">eqv?</font><font face="serif"> 
and </font><font face="monospace">equal?</font><font face="serif"> 
are not meaningful when applied to streams.  For instance, the 
expression </font><font face="monospace">(define s ((stream-lambda 
() stream-null)))</font><font face="serif"> defines </font><font face="monospace">s</font><font face="serif"> 
as the null stream, and </font><font face="monospace">(stream-null? 
s)</font><font face="serif"> is </font><font face="monospace">#t</font><font face="serif">, but </font><font face="monospace">(eq? 
s stream-null)</font><font face="serif"> is </font><font face="monospace">#f</font><font face="serif">.  
To determine if two streams are equal, it is necessary to evaluate the 
elements in their common prefixes, reporting </font><font face="monospace">#f</font><font face="serif"> if two elements ever differ and </font><font face="monospace">#t</font><font face="serif"> 
if both streams are exhausted at the same time.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define (stream-equal? eql? xs ys)
  (cond ((and (stream-null? xs)
              (stream-null? ys)) #t)
        ((or (stream-null? xs)
             (stream-null? ys)) #f)
        ((not (eql? (stream-car xs)
                    (stream-car ys))) #f)
        (else (stream-equal? eql?
                (stream-cdr xs)
                (stream-cdr ys)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">It is generally 
not a good idea to mix lazy streams with eager side-effects, because 
the order in which stream elements are evaluated determines the order 
in which the side-effects occur.  For a simple example, consider 
this side-effecting version of </font><font face="monospace">strm123</font><font face="serif">:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(define strm123-with-side-effects
  (stream-cons (begin (display "one") 1)
    (stream-cons (begin (display "two") 2)
      (stream-cons (begin (display "three") 3)
        stream-null))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The stream 
has elements </font><font face="monospace">1</font><font face="serif"> </font><font face="monospace">2</font><font face="serif"> </font><font face="monospace">3</font><font face="serif">.  
But depending on the order in which stream elements are accessed, </font><font face="monospace">"one"</font><font face="serif">, </font><font face="monospace">"two"</font><font face="serif"> 
and </font><font face="monospace">"three"</font><font face="serif"> could be printed in any order.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Since the performance 
of streams can be very poor, normal (eager) lists should be preferred 
to streams unless there is some compelling reason to the contrary.  
For instance, computing pythagorean triples with streams</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(stream-ref
  (stream-of (list a b c)
    (n in (stream-from 1))
    (a in (stream-range 1 n))
    (b in (stream-range a n))
    (c is (- n a b))
    (= (+ (* a a) (* b b)) (* c c)))
  50)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">is about two 
orders of magnitude slower than the equivalent expression using loops.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>(do ((n 1 (+ n 1))) ((&gt; n 228))
  (do ((a 1 (+ a 1))) ((&gt; a n))
    (do ((b a (+ b 1))) ((&gt; b n))
      (let ((c (- n a b)))
        (if (= (+ (* a a) (* b b)) (* c c))
            (display (list a b c)))))))</pre></font></font></font></p>

<h1><font face="serif"><font face="serif">Implementation</font></font></h1>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Bird and Wadler 
describe streams as either null or a pair with a stream in the tail:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">
&#945; list :: null | &#945; * &#945; list</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">That works 
in a purely functional language such as Miranda
or Haskell because the entire language is lazy.  In 
an eager language like ML or Scheme, of course, it&#8217;s just a normal, 
eager list.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Using ML, Wadler, 
Taha and MacQueen give the type of even streams as:</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>datatype 'a stream_
  = Nil_
  | Cons_ of 'a * 'a stream
withtype 'a stream
  = 'a stream_ susp;</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Their </font><font face="monospace">susp</font><font face="serif"> 
type is similar to Scheme&#8217;s </font><font face="monospace">promise</font><font face="serif"> type.  Since Scheme conflates 
the notions of record and type (the only way to create a new type disjoint 
from all other types is to create a record), it is necessary to distribute 
the suspension through the two constructors of the stream data type:</font></font></font></p>

<p><font face="serif"><font face="serif"><font face="monospace"><pre>&#945; stream
  :: (promise stream-null)
  |  (promise (&#945; stream-pair))</pre></font></font></font></p>

<p><font face="serif"><font face="serif"><font face="monospace"><pre>&#945; stream-pair
  :: &#945; × (&#945; stream)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">That type captures 
the systematic suspension of recursive promises that is the essence 
of &#8220;streamness.&#8221;  But it doesn&#8217;t quite work, because Scheme 
is eager rather than lazy, and both the car and the cdr of the stream 
are evaluated too early.  So the final type of streams delays both 
the car and the cdr of the stream-pair:</font></font></font></p>

<p><font face="serif"><font face="serif"><font face="monospace"><pre>&#945; stream
  :: (promise stream-null)
  |  (promise (&#945; stream-pair))</pre></font></font></font></p>

<p><font face="serif"><font face="serif"><font face="monospace"><pre>&#945; stream-pair
  :: (promise &#945;) × (promise (&#945; stream))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">The two outer 
promises, in the </font><font face="monospace">stream</font><font face="serif"> type, provide streams without memoization.  
The two inner promises, in the </font><font face="monospace">stream-pair</font><font face="serif"> type, add the memoization that is 
characteristic of streams in modern functional languages.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Lists provide 
seven primitive operations: the two constructors </font><font face="monospace">'()</font><font face="serif"> and </font><font face="monospace">cons</font><font face="serif">, the type predicates </font><font face="monospace">list?</font><font face="serif">, </font><font face="monospace">null?</font><font face="serif"> and </font><font face="monospace">pair?</font><font face="serif">, and the accessors </font><font face="monospace">car</font><font face="serif"> and </font><font face="monospace">cdr</font><font face="serif"> for pairs.  All other list operations 
can be derived from those primitives.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">It would seem 
that the same set of primitives could apply to streams, but in fact 
one additional primitive is required.  André van Tonder describes 
the reason in his discussion of the promise data type.  The promises 
of R6RS are inadequate to support iterative algorithms because each 
time a promise is called iteratively it binds the old promise in the 
closure that defines the new promise (so the old promise can be forced 
later, if requested).  However, in the case of iteration, the old 
promise becomes unreachable, so instead of creating a new promise that 
binds the old promise within, it is better to mutate the promise; that 
way, no space is wasted by the old promise.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Van Tonder 
describes this new promise type, and provides a recipe for its use: 
all constructors are wrapped with </font><font face="monospace">delay</font><font face="serif">, all accessors are wrapped with </font><font face="monospace">force</font><font face="serif">, 
and all function bodies are wrapped with </font><font face="monospace">lazy</font><font face="serif">.  Given the seven primitives 
above, the first two parts of van Tonder&#8217;s recipe are simple: the 
two constructors </font><font face="monospace">stream-null</font><font face="serif"> and </font><font face="monospace">stream-pair</font><font face="serif"> hide </font><font face="monospace">delay</font><font face="serif">, and the two accessors </font><font face="monospace">stream-car</font><font face="serif"> 
and </font><font face="monospace">stream-cdr</font><font face="serif"> 
hide </font><font face="monospace">force</font><font face="serif"> 
(</font><font face="monospace">stream-null?</font><font face="serif"> 
and </font><font face="monospace">stream-pair?</font><font face="serif"> also hide </font><font face="monospace">force</font><font face="serif">, so they can distinguish the two constructors 
of the stream type).</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Although the 
new promise type prevents a space leak, it creates a new problem: there 
is no place to hide the </font><font face="monospace">lazy</font><font face="serif"> that is the third part of van Tonder&#8217;s 
recipe.  SRFI-40 solved this problem by exposing it (actually, 
it exposed </font><font face="monospace">delay</font><font face="serif">, which was incorrect).  But that 
violates good software engineering by preventing the stream 
data type from being fully abstract.  The solution of SRFI-41 is 
to create a new primitive, </font><font face="monospace">stream-lambda</font><font face="serif">, that returns a function that hides </font><font face="monospace">lazy</font><font face="serif">.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Besides hiding </font><font face="monospace">lazy</font><font face="serif"> 
and making the types work out correctly, </font><font face="monospace">stream-lambda</font><font face="serif"> is obvious and easy-to-use for competent 
Scheme programmers, especially when augmented with the syntactic sugar 
of </font><font face="monospace">define-stream</font><font face="serif"> and named </font><font face="monospace">stream-let</font><font face="serif">.  The alternative of exposing </font><font face="monospace">stream-lazy</font><font face="serif"> 
would be less clear and harder to use.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">One of the 
hardest tasks when writing any program library is to decide what to 
include and, more importantly, what to exclude.  One important 
guideline is minimalism, since once an operator enters a library it 
must remain forever: <i>Il semble que la perfection soit atteinte non 
quand il n&#8217;y a plus rien à ajouter, mais quand il n&#8217;y a plus rien 
à retrancher</i>.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Since streams 
are substantially slower than lists (the stream primitives require numerous 
type conversions, and list operations in most Scheme implementations 
are heavily optimized), most programmers will use streams only when 
the sequence of elements is truly infinite (such as mathematical series) 
or when there is some clear advantage of laziness (such as reducing 
the number of passes though a large data set).  Thus, the library 
is biased toward functions that work with infinite streams left-to-right.  
In particular, there is no right-fold; if you need to materialize an entire stream, 
it&#8217;s best to use a list.</font></font></font></p>

<h2><font face="serif"><font face="serif">Implementation of <font face="monospace">(streams primitive)</font></font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(library (streams primitive)</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (export stream-null stream-cons stream? stream-null? stream-pair?
          stream-car stream-cdr stream-lambda)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (import (rnrs) (rnrs mutable-pairs))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-record-type (stream-type make-stream stream?)
    (fields (mutable box stream-promise stream-promise!)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-lazy
    (syntax-rules ()
      ((stream-lazy expr)
        (make-stream
          (cons 'lazy (lambda () expr))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-eager expr)
    (make-stream
      (cons 'eager expr)))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-delay
    (syntax-rules ()
      ((stream-delay expr)
        (stream-lazy (stream-eager expr)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-force promise)
    (let ((content (stream-promise promise)))
      (case (car content)
        ((eager) (cdr content))
        ((lazy)  (let* ((promise* ((cdr content)))
                        (content  (stream-promise promise)))
                   (if (not (eqv? (car content) 'eager))
                       (begin (set-car! content (car (stream-promise promise*)))
                              (set-cdr! content (cdr (stream-promise promise*)))
                              (stream-promise! promise* content)))
                   (stream-force promise))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define stream-null (stream-delay (cons 'stream 'null)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-record-type (stream-pare-type make-stream-pare stream-pare?)
    (fields (immutable kar stream-kar) (immutable kdr stream-kdr)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-pair? obj)
    (and (stream? obj) (stream-pare? (stream-force obj))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-null? obj)
    (and (stream? obj)
         (eqv? (stream-force obj)
               (stream-force stream-null))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-cons
    (syntax-rules ()
      ((stream-cons obj strm)
        (stream-eager (make-stream-pare (stream-delay obj) (stream-lazy strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-car strm)
    (cond ((not (stream? strm)) (error 'stream-car "non-stream"))
          ((stream-null? strm) (error 'stream-car "null stream"))
          (else (stream-force (stream-kar (stream-force strm))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-cdr strm)
    (cond ((not (stream? strm)) (error 'stream-cdr "non-stream"))
          ((stream-null? strm) (error 'stream-cdr "null stream"))
          (else (stream-kdr (stream-force strm)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-lambda
    (syntax-rules ()
      ((stream-lambda formals body0 body1 ...)
        (lambda formals (stream-lazy (let () body0 body1 ...)))))))</pre></font></font></font></p>

<h2><font face="serif"><font face="serif">Implementation of <font face="monospace">(streams derived)</font></font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(library (streams derived)</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (export stream-null stream-cons stream? stream-null? stream-pair? stream-car
          stream-cdr stream-lambda define-stream list-&gt;stream port-&gt;stream stream
          stream-&gt;list stream-append stream-concat stream-constant stream-drop
          stream-drop-while stream-filter stream-fold stream-for-each stream-from
          stream-iterate stream-length stream-let stream-map stream-match _
          stream-of stream-range stream-ref stream-reverse stream-scan stream-take
          stream-take-while stream-unfold stream-unfolds stream-zip)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (import (rnrs) (streams primitive))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax define-stream
    (syntax-rules ()
      ((define-stream (name . formal) body0 body1 ...)
        (define name (stream-lambda formal body0 body1 ...)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (list-&gt;stream objs)
    (define list-&gt;stream
      (stream-lambda (objs)
        (if (null? objs)
            stream-null
            (stream-cons (car objs) (list-&gt;stream (cdr objs))))))
    (if (not (list? objs))
        (error 'list-&gt;stream "non-list argument")
        (list-&gt;stream objs)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (port-&gt;stream . port)
    (define port-&gt;stream
      (stream-lambda (p)
        (let ((c (read-char p)))
          (if (eof-object? c)
              stream-null
              (stream-cons c (port-&gt;stream p))))))
    (let ((p (if (null? port) (current-input-port) (car port))))
      (if (not (input-port? p))
          (error 'port-&gt;stream "non-input-port argument")
          (port-&gt;stream p))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream
    (syntax-rules ()
      ((stream) stream-null)
      ((stream x y ...) (stream-cons x (stream y ...)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-&gt;list . args)
    (let ((n (if (= 1 (length args)) #f (car args)))
          (strm (if (= 1 (length args)) (car args) (cadr args))))
      (cond ((not (stream? strm)) (error 'stream-&gt;list "non-stream argument"))
            ((and n (not (integer? n))) (error 'stream-&gt;list "non-integer count"))
            ((and n (negative? n)) (error 'stream-&gt;list "negative count"))
            (else (let loop ((n (if n n -1)) (strm strm))
                    (if (or (zero? n) (stream-null? strm))
                        '()
                        (cons (stream-car strm) (loop (- n 1) (stream-cdr strm)))))))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-append . strms)
    (define stream-append
      (stream-lambda (strms)
        (cond ((null? (cdr strms)) (car strms))
              ((stream-null? (car strms)) (stream-append (cdr strms)))
              (else (stream-cons (stream-car (car strms))
                                 (stream-append (cons (stream-cdr (car strms)) (cdr strms))))))))
    (cond ((null? strms) stream-null)
          ((exists (lambda (x) (not (stream? x))) strms)
            (error 'stream-append "non-stream argument"))
          (else (stream-append strms))))</pre></font></font></font></p>
<font face="serif"><font face="serif">  
</font></font><p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-concat strms)
    (define stream-concat
      (stream-lambda (strms)
        (cond ((stream-null? strms) stream-null)
              ((not (stream? (stream-car strms)))
                (error 'stream-concat "non-stream object in input stream"))
              ((stream-null? (stream-car strms))
                (stream-concat (stream-cdr strms)))
              (else (stream-cons
                      (stream-car (stream-car strms))
                      (stream-concat
                        (stream-cons (stream-cdr (stream-car strms)) (stream-cdr strms))))))))
    (if (not (stream? strms))
        (error 'stream-concat "non-stream argument")
        (stream-concat strms)))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define stream-constant
    (stream-lambda objs
      (cond ((null? objs) stream-null)
            ((null? (cdr objs)) (stream-cons (car objs) (stream-constant (car objs))))
            (else (stream-cons (car objs)
                               (apply stream-constant (append (cdr objs) (list (car objs)))))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-drop n strm)
    (define stream-drop
      (stream-lambda (n strm)
        (if (or (zero? n) (stream-null? strm))
            strm
            (stream-drop (- n 1) (stream-cdr strm)))))
    (cond ((not (integer? n)) (error 'stream-drop "non-integer argument"))
          ((negative? n) (error 'stream-drop "negative argument"))
          ((not (stream? strm)) (error 'stream-drop "non-stream argument"))
          (else (stream-drop n strm))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-drop-while pred? strm)
    (define stream-drop-while
      (stream-lambda (strm)
        (if (and (stream-pair? strm) (pred? (stream-car strm)))
            (stream-drop-while (stream-cdr strm))
            strm)))
    (cond ((not (procedure? pred?)) (error 'stream-drop-while "non-procedural argument"))
          ((not (stream? strm)) (error 'stream-drop-while "non-stream argument"))
          (else (stream-drop-while strm))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-filter pred? strm)
    (define stream-filter
      (stream-lambda (strm)
        (cond ((stream-null? strm) stream-null)
              ((pred? (stream-car strm))
                (stream-cons (stream-car strm) (stream-filter (stream-cdr strm))))
              (else (stream-filter (stream-cdr strm))))))
    (cond ((not (procedure? pred?)) (error 'stream-filter "non-procedural argument"))
          ((not (stream? strm)) (error 'stream-filter "non-stream argument"))
          (else (stream-filter strm))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-fold proc base strm)
    (cond ((not (procedure? proc)) (error 'stream-fold "non-procedural argument"))
          ((not (stream? strm)) (error 'stream-fold "non-stream argument"))
          (else (let loop ((base base) (strm strm))
                  (if (stream-null? strm)
                      base
                      (loop (proc base (stream-car strm)) (stream-cdr strm)))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-for-each proc . strms)
    (define (stream-for-each strms)
      (if (not (exists stream-null? strms))
          (begin (apply proc (map stream-car strms))
                 (stream-for-each (map stream-cdr strms)))))
    (cond ((not (procedure? proc)) (error 'stream-for-each "non-procedural argument"))
          ((null? strms) (error 'stream-for-each "no stream arguments"))
          ((exists (lambda (x) (not (stream? x))) strms)
            (error 'stream-for-each "non-stream argument"))
          (else (stream-for-each strms))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-from first . step)
    (define stream-from
      (stream-lambda (first delta)
        (stream-cons first (stream-from (+ first delta) delta))))
    (let ((delta (if (null? step) 1 (car step))))
      (cond ((not (number? first)) (error 'stream-from "non-numeric starting number"))
            ((not (number? delta)) (error 'stream-from "non-numeric step size"))
            (else (stream-from first delta)))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-iterate proc base)
    (define stream-iterate
      (stream-lambda (base)
        (stream-cons base (stream-iterate (proc base)))))
    (if (not (procedure? proc))
        (error 'stream-iterate "non-procedural argument")
        (stream-iterate base)))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-length strm)
    (if (not (stream? strm))
        (error 'stream-length "non-stream argument")
        (let loop ((len 0) (strm strm))
          (if (stream-null? strm)
              len
              (loop (+ len 1) (stream-cdr strm))))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-let
    (syntax-rules ()
      ((stream-let tag ((name val) ...) body1 body2 ...)
       ((letrec ((tag (stream-lambda (name ...) body1 body2 ...))) tag) val ...))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-map proc . strms)
    (define stream-map
      (stream-lambda (strms)
        (if (exists stream-null? strms)
            stream-null
            (stream-cons (apply proc (map stream-car strms))
                         (stream-map (map stream-cdr strms))))))
    (cond ((not (procedure? proc)) (error 'stream-map "non-procedural argument"))
          ((null? strms) (error 'stream-map "no stream arguments"))
          ((exists (lambda (x) (not (stream? x))) strms)
            (error 'stream-map "non-stream argument"))
          (else (stream-map strms))))</pre></font></font></font></p>
<font face="serif"><font face="serif">  
</font></font><p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define-syntax stream-match
    (syntax-rules ()
      ((stream-match strm-expr clause ...)
        (let ((strm strm-expr))
          (cond
            ((not (stream? strm)) (error 'stream-match "non-stream argument"))
            ((stream-match-test strm clause) =&gt; car) ...
            (else (error 'stream-match "pattern failure")))))))</font></font></font></pre><p></p>
<font face="serif"><font face="serif"> 
</font></font><p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-match-test
    (syntax-rules ()
      ((stream-match-test strm (pattern fender expr))
        (stream-match-pattern strm pattern () (and fender (list expr))))
      ((stream-match-test strm (pattern expr))
        (stream-match-pattern strm pattern () (list expr)))))</pre></font></font></font></p>
<font face="serif"><font face="serif"> 
</font></font><p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define-syntax stream-match-pattern 
    (lambda (x)
      (define (wildcard? x)
        (and (identifier? x)
             (free-identifier=? x (syntax _))))
      (syntax-case x () 
        ((stream-match-pattern strm () (binding ...) body)
          (syntax (and (stream-null? strm) (let (binding ...) body))))
        ((stream-match-pattern strm (w? . rest) (binding ...) body)
          (wildcard? #'w?) 
          (syntax (and (stream-pair? strm)
                       (let ((strm (stream-cdr strm)))
                         (stream-match-pattern strm rest (binding ...) body)))))
        ((stream-match-pattern strm (var . rest) (binding ...) body)
          (syntax (and (stream-pair? strm)
                       (let ((temp (stream-car strm)) (strm (stream-cdr strm))) 
                         (stream-match-pattern strm rest ((var temp) binding ...) body)))))
        ((stream-match-pattern strm w? (binding ...) body)
          (wildcard? #'w?)
          (syntax (let (binding ...) body)))
        ((stream-match-pattern strm var (binding ...) body) 
          (syntax (let ((var strm) binding ...) body))))))</font></font></font></pre><p></p>
<font face="serif"><font face="serif">  
</font></font><p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-of
    (syntax-rules ()
      ((_ expr rest ...)
        (stream-of-aux expr stream-null rest ...))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define-syntax stream-of-aux
    (syntax-rules (in is)
      ((stream-of-aux expr base)
        (stream-cons expr base))
      ((stream-of-aux expr base (var in stream) rest ...)
        (stream-let loop ((strm stream))
          (if (stream-null? strm)
              base
              (let ((var (stream-car strm)))
                (stream-of-aux expr (loop (stream-cdr strm)) rest ...)))))
      ((stream-of-aux expr base (var is exp) rest ...)
        (let ((var exp)) (stream-of-aux expr base rest ...)))
      ((stream-of-aux expr base pred? rest ...)
        (if pred? (stream-of-aux expr base rest ...) base))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-range first past . step)
    (define stream-range
      (stream-lambda (first past delta lt?)
        (if (lt? first past)
            (stream-cons first (stream-range (+ first delta) past delta lt?))
            stream-null)))
    (cond ((not (number? first)) (error 'stream-range "non-numeric starting number"))
          ((not (number? past)) (error 'stream-range "non-numeric ending number"))
          (else (let ((delta (cond ((pair? step) (car step)) ((&lt; first past) 1) (else -1))))
                  (if (not (number? delta))
                      (error 'stream-range "non-numeric step size")
                      (let ((lt? (if (&lt; 0 delta) &lt; &gt;)))
                        (stream-range first past delta lt?)))))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-ref strm n)
    (cond ((not (stream? strm)) (error 'stream-ref "non-stream argument"))
          ((not (integer? n)) (error 'stream-ref "non-integer argument"))
          ((negative? n) (error 'stream-ref "negative argument"))
          (else (let loop ((strm strm) (n n))
                  (cond ((stream-null? strm) (error 'stream-ref "beyond end of stream"))
                        ((zero? n) (stream-car strm))
                        (else (loop (stream-cdr strm) (- n 1))))))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-reverse strm)
    (define stream-reverse
      (stream-lambda (strm rev)
        (if (stream-null? strm)
            rev
            (stream-reverse (stream-cdr strm) (stream-cons (stream-car strm) rev)))))
    (if (not (stream? strm))
        (error 'stream-reverse "non-stream argument")
        (stream-reverse strm stream-null)))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-scan proc base strm)
    (define stream-scan
      (stream-lambda (base strm)
        (if (stream-null? strm)
            (stream base)
            (stream-cons base (stream-scan (proc base (stream-car strm)) (stream-cdr strm))))))
    (cond ((not (procedure? proc)) (error 'stream-scan "non-procedural argument"))
          ((not (stream? strm)) (error 'stream-scan "non-stream argument"))
          (else (stream-scan base strm))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-take n strm)
    (define stream-take
      (stream-lambda (n strm)
        (if (or (stream-null? strm) (zero? n))
            stream-null
            (stream-cons (stream-car strm) (stream-take (- n 1) (stream-cdr strm))))))
    (cond ((not (stream? strm)) (error 'stream-take "non-stream argument"))
          ((not (integer? n)) (error 'stream-take "non-integer argument"))
          ((negative? n) (error 'stream-take "negative argument"))
          (else (stream-take n strm))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-take-while pred? strm)
    (define stream-take-while
      (stream-lambda (strm)
        (cond ((stream-null? strm) stream-null)
              ((pred? (stream-car strm))
                (stream-cons (stream-car strm) (stream-take-while (stream-cdr strm))))
              (else stream-null))))
    (cond ((not (stream? strm)) (error 'stream-take-while "non-stream argument"))
          ((not (procedure? pred?)) (error 'stream-take-while "non-procedural argument"))
          (else (stream-take-while strm))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (define (stream-unfold mapper pred? generator base)
    (define stream-unfold
      (stream-lambda (base)
        (if (pred? base)
            (stream-cons (mapper base) (stream-unfold (generator base)))
            stream-null)))
    (cond ((not (procedure? mapper)) (error 'stream-unfold "non-procedural mapper"))
          ((not (procedure? pred?)) (error 'stream-unfold "non-procedural pred?"))
          ((not (procedure? generator)) (error 'stream-unfold "non-procedural generator"))
          (else (stream-unfold base))))</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-unfolds gen seed)
    (define (len-values gen seed)
      (call-with-values
        (lambda () (gen seed))
        (lambda vs (- (length vs) 1))))
    (define unfold-result-stream
      (stream-lambda (gen seed)
        (call-with-values
          (lambda () (gen seed))
          (lambda (next . results)
            (stream-cons results (unfold-result-stream gen next))))))
    (define result-stream-&gt;output-stream
      (stream-lambda (result-stream i)
        (let ((result (list-ref (stream-car result-stream) (- i 1))))
          (cond ((pair? result)
                  (stream-cons
                    (car result)
                    (result-stream-&gt;output-stream (stream-cdr result-stream) i)))
                ((not result)
                  (result-stream-&gt;output-stream (stream-cdr result-stream) i))
                ((null? result) stream-null)
                (else (error 'stream-unfolds "can't happen"))))))
    (define (result-stream-&gt;output-streams result-stream)
      (let loop ((i (len-values gen seed)) (outputs '()))
        (if (zero? i)
            (apply values outputs)
            (loop (- i 1) (cons (result-stream-&gt;output-stream result-stream i) outputs)))))
    (if (not (procedure? gen))
        (error 'stream-unfolds "non-procedural argument")
        (result-stream-&gt;output-streams (unfold-result-stream gen seed))))</font></font></font></pre><p></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"></font></font></font></p><pre><font face="serif"><font face="serif"><font face="monospace">  (define (stream-zip . strms)
    (define stream-zip
      (stream-lambda (strms)
        (if (exists stream-null? strms)
            stream-null
            (stream-cons (map stream-car strms) (stream-zip (map stream-cdr strms))))))
    (cond ((null? strms) (error 'stream-zip "no stream arguments"))
          ((exists (lambda (x) (not (stream? x))) strms)
            (error 'stream-zip "non-stream argument"))
          (else (stream-zip strms)))))</font></font></font></pre><p></p>

<h2><font face="serif"><font face="serif">Implementation of <font face="monospace">(streams)</font></font></font></h2>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace">(library (streams)</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (export stream-null stream-cons stream? stream-null? stream-pair? stream-car
          stream-cdr stream-lambda define-stream list-&gt;stream port-&gt;stream stream
          stream-&gt;list stream-append stream-concat stream-constant stream-drop
          stream-drop-while stream-filter stream-fold stream-for-each stream-from
          stream-iterate stream-length stream-let stream-map stream-match _
          stream-of stream-range stream-ref stream-reverse stream-scan stream-take
          stream-take-while stream-unfold stream-unfolds stream-zip)</pre></font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="monospace"><pre>  (import (streams primitive) (streams derived)))</pre></font></font></font></p>

<h1><font face="serif"><font face="serif">Acknowledgements</font></font></h1>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Jos Koot sharpened 
my thinking during many e-mail discussions, suggested several discussion 
points in the text, and contributed the final version of </font><font face="monospace">stream-match</font><font face="serif">.  
Michael Sperber and Abdulaziz Ghuloum gave advice on R6RS.</font></font></font></p>

<h1><font face="serif"><font face="serif">References</font></font></h1>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Harold Abelson 
and Gerald Jay Sussman with Julie Sussman.  <i>Structure and Interpretation 
of Computer Programs</i>.  MIT Press, Cambridge, Massachusetts.  
Second edition, 1996.  </font><font face="monospace"><a href="http://mitpress.mit.edu/sicp" target="_blank">mitpress.mit.edu/sicp</a></font><font face="serif">.  The classic text on computer 
science.  Section 3.5 includes extensive discussion of odd streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Anne L. Bewig.  
&#8220;Golden Ratio&#8221; (personal communication).  Homework for the 
high school course <i>Calculus</i>.  Teaching my daughter how to 
calculate the 200<sup>th</sup> element of a continued fraction was a 
moment of sheer joy in the development of the stream libraries.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Philip L. Bewig.  <i>
Scheme Request for Implementation 40: 
A Library of Streams</i>.  August, 2004.  </font><font face="monospace"><a href="http://srfi.schemers.org/srfi-40" target="_blank">srfi.schemers.org/srfi-40</a></font><font face="serif">.  Describes an implementation 
of the </font><font face="monospace">stream</font><font face="serif"> 
data type. </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Richard Bird 
and Philip Wadler.  <i>Introduction to Functional Programming</i>.  
Prentice Hall, 1988.  The classic text on functional programming.  
Even streams are discussed in the context of purely functional programming.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">William H. 
Burge.  <i>Recursive Programming Techniques</i>.  Addison-Wesley, 
1975.  An early text on functional programming, and still one of 
the best, though the terminology is dated.  Discusses even streams 
in Section 3.10.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Jeremy Gibbons, 
David Lester and Richard Bird, &#8220;Functional Pearl: Enumerating the 
Rationals,&#8221; under consideration for publication in <i>Journal of Functional 
Programming</i>.  </font><font face="monospace"><a href="http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf" target="_blank">http://web.comlab.ox.ac.uk<wbr>/oucl/work/jeremy.gibbons<wbr>/publications/rationals.pdf</a></font><font face="serif">.  Discusses a series of expressions 
that enumerate the rational numbers without duplicates.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Carl Hewitt. 
&#8220;Viewing control structures as patterns of passing messages,&#8221; in <i>
Journal of Artificial Intelligence</i>, Volume 8, Number 3 (June, 1977), 
pp 323-364.  Also published as Artificial Intelligence Memo 410 
by the Massachusetts Institute of Technology, </font><font face="monospace"><a href="ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-410.pdf" target="_blank">ftp://publications.ai.mit.edu<wbr>/ai-publications/pdf/AIM-410<wbr>.pdf</a></font><font face="serif">.  Describes the Actor message-passing 
system; one of the examples used is the </font><font face="monospace">same-fringe?</font><font face="serif"> problem.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Peter J. Landin.  
&#8220;A correspondence between ALGOL 60 and Church&#8217;s lambda-notation: 
Part I,&#8221;  <i>Communications of the ACM</i>, Volume 8, Number 
2, February 1965., pages 89&#8211;101.  The seminal description of 
streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Joe Marshall.  
&#8220;Stream problem redux&#8221;, from <i>Usenet 
comp.lang.scheme</i>, June 28, 2002.  </font><font face="monospace"><a href="http://groups.google.com/group/comp.lang.scheme/msg/db4b4a1f33e3eea8" target="_blank">groups.google.com/group/comp<wbr>.lang.scheme/msg/db4b4a1f33e3ee<wbr>a8</a></font><font face="serif">.  The original post on </font><font face="monospace">comp.lang.scheme</font><font face="serif"> 
that describes the </font><font face="monospace">times3</font><font face="serif"> problem.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Chris Okasaki.  <i>
Purely Functional Data Structures</i>.  Cambridge University Press, 
2003.  Revised version of Okasaki&#8217;s thesis <i>Purely Functional 
Data Structures</i>, Carnegie-Mellon University, 1996, </font><font face="monospace"><a href="http://www.cs.cmu.edu/%7Erwh/theses/okasaki.pdf" target="_blank">www.cs.cmu.edu/~rwh/theses<wbr>/okasaki.pdf</a></font><font face="serif">.  Provides a strong defense of 
laziness, and describes several data structures that exploit laziness, 
including streams and queues.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Stephen K. 
Park and Keith W. Miller.  &#8220;Random number generators: good ones 
are hard to find,&#8221; <i>Communications of the ACM</i>, Volume 31, Issue 
10 (October 1988), pages 1192&#8211;1201.  Describes a minimal standard 
random number generator. </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Simon Peyton-Jones, 
et al, editors.  <i>Haskell 98: Haskell 98 Language and Libraries: 
The Revised Report</i>.  December 2002.  </font><font face="monospace"><a href="http://www.haskell.org/onlinereport" target="_blank">www.haskell.org/onlinereport</a></font><font face="serif">.  Haskell is the prototypical 
purely functional language, and includes even streams, which it calls 
lists, as its fundamental structured data type.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Chris Reade.  <i>
Elements of Functional Programming</i>.  Addison-Wesley, April 
1989.  A textbook on functional programming.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Antoine de 
Saint-Exupéry. Chapter III &#8220;L&#8217;Avion&#8221; of <i>Terre des Hommes</i>.  
1939.  &#8220;Perfection is achieved, not when there is nothing more 
to add, but when there is nothing left to take away.&#8221;</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Dorai Sitaram.  <i>
Teach Yourself Scheme in Fixnum Days</i>.  </font><font face="monospace"><a href="http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html" target="_blank">www.ccs.neu.edu/home/dorai/t-y<wbr>-scheme/t-y-scheme.html</a></font><font face="serif">.  A useful introduction to Scheme; 
includes generator and co-routine solutions to the </font><font face="monospace">same-fringe?</font><font face="serif"> problem.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Michael Sperber, 
R. Kent Dybvig, Matthew Flatt, and Anton von Straaten, editors.  <i>

Revised</i><sup><i>6</i></sup><i> Report on the Algorithmic Language 
Scheme</i>.  September 26, 2007. </font><font face="monospace"><a href="http://www.r6rs.org/" target="_blank">www.r6rs.org</a></font><font face="serif">.  The standard definition of 
the Scheme programming language.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">André van 
Tonder.  <i>Scheme Request for Implementation 45: 
Primitives for Expressing Iterative Lazy Algorithms</i>.  </font><font face="monospace"><a href="http://srfi.schemers.org/srfi-45" target="_blank">srfi.schemers.org/srfi-45</a></font><font face="serif">.  
April, 2004.  Describes the problems inherent in the </font><font face="monospace">promise</font><font face="serif"> 
data type of R5RS (also present in R6RS), and provides the alternate </font><font face="monospace">promise</font><font face="serif"> 
data type used in the stream primitives.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Philip Wadler.  
&#8220;How to replace failure by a list of successes,&#8221; in <i>Proceedings 
of the conference on functional programming languages and computer architecture</i>, 
Nancy, France, 1985, pages 113&#8211;128.  Describes the &#8220;list of 
successes&#8221; technique for implementing backtracking algorithms using 
streams.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">Philip Wadler, 
Walid Taha, and David MacQueen, &#8220;How to add laziness to a strict language 
without even being odd.&#8221;  1998 ACM SIGPLAN Workshop on ML, pp. 24ff.  </font><font face="monospace"><a href="http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps" target="_blank">homepages.inf.ed.ac.uk/wadler<wbr>/papers/lazyinstrict/lazyinstri<wbr>ct.ps</a></font><font face="serif">.  Describes odd and even styles 
of lazy evaluation, and shows how to add lazy evaluation to the strict 
functional language SML. </font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">All cited web 
pages visited during September 2007.</font></font></font></p>

<h1><font face="serif"><font face="serif">Copyright</font></font></h1>

<p align="justify"><font face="serif"><font face="serif"><font face="serif">
Copyright (C) Philip L. Bewig (2007). All Rights Reserved.</font></font></font></p>

<p align="justify">
<font face="serif"><font face="serif"><font face="serif">Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:</font></font></font></p>

<p align="justify">
<font face="serif"><font face="serif"><font face="serif">The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.</font></font></font></p>

<p align="justify">
<font face="serif"><font face="serif"><font face="serif">THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.</font></font></font></p>

<p align="justify"><font face="serif"><font face="serif"><font face="serif"><font face="serif">Several files related to this document are
available from</font>
<font face="monospace">srfi.schemers.org/srfi-41</font><font face="serif">:
A version of this document suitable for printing is available at</font>
<font face="monospace"><a href="http://srfi.schemers.org/srfi-41/streams.pdf">streams.pdf</a></font><font face="serif">.
The complete source corresponding to the three Appendices is available in files</font>
<font face="monospace"><a href="http://srfi.schemers.org/srfi-41/streams.ss">streams.ss</a></font><font face="serif">,
</font><font face="monospace"><a href="http://srfi.schemers.org/srfi-41/primitive.ss">primitive.ss</a></font><font face="serif">, and
</font><font face="monospace"><a href="http://srfi.schemers.org/srfi-41/derived.ss">derived.ss</a></font><font face="serif">.
Samples from the text are available at
</font><font face="monospace"><a href="http://srfi.schemers.org/srfi-41/samples.ss">samples.ss</a></font><font face="serif">,
and a test suite is available at</font>
<font face="monospace"><a href="http://srfi.schemers.org/srfi-41/r6rs-test.ss">r6rs-test.ss</a></font><font face="serif">.
Source code and tests for R5RS are available at</font>
<font face="monospace"><a href="http://srfi.schemers.org/srfi-41/r5rs.ss">r5rs.ss</a></font><font face="serif">,
and</font> <font face="monospace"><a href="http://srfi.schemers.org/srfi-41/r5rs-test.ss">r5rs-test.ss</a></font><font face="serif">.</font></font></font></font></p>

<hr>
<address><font face="serif"><font face="serif"><font face="serif">Editor: <a href="mailto:srfi-editors%20at%20srfi%20dot%20schemers%20dot%20org">Michael Sperber</a></font></font></font></address>

</body></html>
